Kids With the Greatest Number of Candies Leetcode Solution

In the problem “Kids With the Greatest Number of Candies”, we are given an array of integers that represents the number of chocolates some children have got and some extra candies that can be distributed in any manner. Now, we need to find:

• Can every child have the greatest number of chocolates after distribution(either with majority or jointly)?

We need to print this possibility in the form of a boolean vector.

Example

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5

false true true true true

Explanation

1st child: Even if we gave all 5 extra candies to the first child, it will have 6 candies < 7(5th child). So, we print false for it.

2nd child: We give all 5 extra candies to this child, making its count to 9 > 7(5th child). So, we print true for it.

Similarly, for the third, fourth and fifth child it is easy to see that they can have the greatest number of candies after optimal distribution.

Approach(Greedy)

In the problem, we are independent of our choice to distribute the extra candies. The optimal way to decide for any child would be to give it all the extra candies and then check the required condition. Consider, we need to find the result for any ith child. Now, the maximum amount of candies that can be given to it is equal to the total extra candies.

Therefore, the total number of candies that can be possessed by the ith child = a[i] + extra candies. If this value is greater than the maximum element in the array before distribution, we can conclude that this child can have the most candies after distribution. Since we choose to give all the extra candies to the ith child only, this approach is greedy.

Algorithm

1. Find the maximum of the array and store it as maxCandies
2. Initialize a boolean result array
3. Run a loop from the start of the array to its end:
   1. If the current number of candies of ith child + extra candies is greater than or equal to maxCandies:
      1. Set the result of this child as true, false otherwise
4. Print the result

Implementation of algorithm to find Kids With the Greatest Number of Candies

C++ Program

#include <bits/stdc++.h>
using namespace std;

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

Java Program

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}

false true true true true

Complexity Analysis of finding Kids With the Greatest Number of Candies

Time Complexity

O(N), N = size of the array. As we traverse the whole array once.

Space complexity

O(N), As we save the result of every child in a separate array.