We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Greedy
- Candies
- Discussions
Candies
Candies
Sort by
recency
|
665 Discussions
|
Please Login in order to post a comment
To solve this problem, we'll use a two-pass approach:
Left to Right Pass: Traverse the list from left to right. If a child has a higher rating than the previous child, increment the candy count for that child based on the previous child's candy count.
Right to Left Pass: Traverse the list from right to left. If a child has a higher rating than the next child, ensure that the current child's candy count is higher than the next child's candy count.
The final candy count for each child will be the maximum of the counts from the two passes.
Here's the PHP code to solve the "Candies" problem:
Explanation
Initialization:
candies
array with 1 candy for each child since each child must get at least one candy.Left to Right Pass:
Right to Left Pass:
Summing Up:
candies
array to get the total number of candies required.This approach ensures that the distribution of candies meets the problem's constraints with a time complexity of (O(n)) and space complexity of (O(n)).
This problem was based on increasing/descreasing sequence and pure observation
I did not sove this problem with dynamic programming, I just looked at the cases and where they fail. You can start from the second student and give more candy to the next student who score more than the first and so on, but we don't get to know what peg to choose when the next student score less from 1 to previous student's candy. So. we do nothing and repeat the process doing the same approach from the end trying to find next incements. Here's the code.
Please tell, why this solution is not working. long candies(int n, vector arr) { long sum = 0; vector c(n, 0); c[0] = 1; for (int i = 1; i < n; i++){ if(arr[i-1] < arr[i]){ c[i] = c[i-1] + 1; } else if(arr[i-1] == arr[i]) c[i] = 1; else{ if(c[i-1] != 1){ c[i] = 1; } else{ c[i] = 1; int start = i; while(c[start] == c[start-1] && start >= 1 && start - 1 >= 0){ c[start-1] += 1; start--; } }
} }
sum = std::accumulate(c.begin(), c.end(), sum }