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

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

- Set the result of this child as

- If the current number of candies of
- 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.