Solution For Candy

The Candy problem on LeetCode is a programming challenge that requires you to distribute candies to children in such a way that every child gets at least one candy, and the total number of candies you distribute is minimal. Here’s a detailed solution that solves this problem using the greedy approach.

Algorithm:

1. First, create an array called “candies” of size n for n children.

2. Set all element values of the candies array to 1, so that each child gets at least one candy.

3. Traverse the array from left to right and compare each child’s ratings with the previous child’s rating.

4. If the current child’s rating is greater than the previous child’s rating, then you add 1 to the candies[i] value (i.e., increase the number of candies to the current child).

5. Traverse the array again from right to left and compare each child’s rating with the next child’s rating.

6. If the current child’s rating is greater than the next child’s rating and the candies[i] value is less than or equal to candies[i+1] (where i is the current position), then you add 1 to the candies[i] value (i.e., increase the number of candies to the current child).

7. Return the sum of all candies values in the candies array.

Python Code:

def candy(ratings):
n = len(ratings)
candies = [1] * n

for i in range(1, n):
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1

for i in range(n-2, -1, -1):
    if ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
        candies[i] = candies[i+1] + 1

return sum(candies)

Test Cases:

Let’s test the function with some input data.

Test Case 1:

ratings = [1,0,2] => output = 5
assert(candy(ratings) == 5)

Explanation:
The optimal distribution should be [2, 1, 2] (where each number represents the number of candies each child gets). Child 1 gets 2 candies because his/her rating is higher than child 2, child 2 gets 1 candy, and child 3 gets 2 candies because his/her rating is higher than child 2.

Test Case 2:

ratings = [1,2,2] => output = 4
assert(candy(ratings) == 4)

Explanation:
The optimal distribution should be [1, 2, 1] (where each number represents the number of candies each child gets). Child 1 gets 1 candy, child 2 gets 2 candies, and child 3 gets 1 candy.

Test Case 3:

ratings = [1,3,4,5,2] => output = 11
assert(candy(ratings) == 11)

Explanation:
The optimal distribution should be [1, 2, 3, 4, 1] (where each number represents the number of candies each child gets). Child 1 gets 1 candy, child 2 gets 2 candies, child 3 gets 3 candies, child 4 gets 4 candies, and child 5 gets 1 candy.

Step by Step Implementation For Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

Solution:

We can solve this problem with a greedy approach. We can give each child a candy, and then keep track of the number of candies that each child has. If we encounter a child with a higher rating, we can give them an extra candy. This will ensure that each child has at least as many candies as their neighbors.

We can keep track of the number of candies each child has in an array. Then, we can iterate through the array and update the candies for each child as we go.

public int candy(int[] ratings) {
    int[] candies = new int[ratings.length];
    Arrays.fill(candies, 1);
    
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    for (int i = ratings.length-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
    }
    
    int sum = 0;
    for (int candy : candies) {
        sum += candy;
    }
    return sum;
}

def candy(ratings):
 candy_count = [1] * len(ratings)
 
 for i in range(1, len(ratings)):
     if ratings[i] > ratings[i-1]:
         candy_count[i] = candy_count[i-1] + 1
 
 for i in range(len(ratings)-2, -1, -1):
     if ratings[i] > ratings[i+1]:
         candy_count[i] = max(candy_count[i], candy_count[i+1] + 1)
 
 return sum(candy_count)

/**
 * @param {number[]} ratings
 * @return {number}
 */
 
/*
This problem can be solved with a greedy approach. 
We can keep track of the number of candies each child should have by iterating through the ratings array. 
If a child has a higher rating than the child to their left, they should have one more candy. 
If a child has a lower rating than the child to their left, they should have one less candy. 
*/
 
var candy = function(ratings) {
    // create an array to store the number of candies each child should have
    let candyCount = new Array(ratings.length).fill(1);
    
    // iterate through the ratings array
    for (let i = 0; i < ratings.length; i++) {
        // if the current child has a higher rating than the child to their left, they should have one more candy
        if (ratings[i] > ratings[i-1]) {
            candyCount[i] = candyCount[i-1] + 1;
        }
    }
    
    // iterate through the ratings array in reverse
    for (let i = ratings.length - 1; i >= 0; i--) {
        // if the current child has a higher rating than the child to their right, they should have one more candy
        if (ratings[i] > ratings[i+1]) {
            candyCount[i] = Math.max(candyCount[i], candyCount[i+1] + 1);
        }
    }
    
    // return the sum of the candyCount array
    return candyCount.reduce((a, b) => a + b);
};

The problem is as follows:

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

#include 
#include 

using namespace std;

class Solution {
public:
    int candy(vector& ratings) {
        int n = ratings.size();
        vector res(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) {
                res[i] = res[i-1] + 1;
            }
        }
        for (int i = n-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                res[i] = max(res[i], res[i+1] + 1);
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += res[i];
        }
        return sum;
    }
};

public class Solution {
    public int Candy(int[] ratings) {
        // create an array to store the number of candies given to each child
        int[] candy = new int[ratings.Length];
        
        // give each child 1 candy to start
        for (int i = 0; i < candy.Length; i++) {
            candy[i] = 1;
        }
        
        // scan from left to right, increasing the number of candies given to a child 
        // if their rating is higher than the child to their left
        for (int i = 1; i < candy.Length; i++) {
            if (ratings[i] > ratings[i-1]) {
                candy[i] = candy[i-1] + 1;
            }
        }
        
        // scan from right to left, increasing the number of candies given to a child 
        // if their rating is higher than the child to their right AND 
        // the number of candies they've been given is less than the child to their right
        for (int i = candy.Length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) {
                candy[i] = candy[i+1] + 1;
            }
        }
        
        // sum up the total number of candies
        int sum = 0;
        for (int i = 0; i < candy.Length; i++) {
            sum += candy[i];
        }
        return sum;
    }
}