Kids With the Greatest Number of Candies

Problem Statement

In this scenario, you are provided with the number of candies different children have and an additional quantity of candies you can distribute freely among them. Specifically, you are given an array candies where each element candies[i] represents the number of candies the i-th child has. Alongside, an integer extraCandies indicates the total extra candies available for distribution. The objective is to determine for each child, if it’s possible for them to have the highest number of candies among all the children, should they receive all the extraCandies.

The result is reflected in a boolean array where each index i corresponds to a child. The value is true if giving all extraCandies to the i-th child results in him or her having the maximum candies, and false otherwise. It is important to note that multiple children might end up having an equal number of maximum candies.

Examples

Example 1

Input:

candies = [2,3,5,1,3], extraCandies = 3

Output:

[true,true,true,false,true]

Explanation:

If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

Example 2

Input:

candies = [4,2,1,1,2], extraCandies = 1

Output:

[true,false,false,false,false]

Explanation:

There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

Example 3

Input:

candies = [12,1,12], extraCandies = 10

Output:

[true,false,true]

Constraints

• n == candies.length
• 2 <= n <= 100
• 1 <= candies[i] <= 100
• 1 <= extraCandies <= 50

Approach and Intuition

Given our understanding of the problem, we can outline the approach as follows:

1. First, identify the current highest number of candies any child has without any distribution of extra candies. This helps set a benchmark for comparison.
2. Iterate through the candies array and for each child calculate the total number of candies they would have if they were given all the extraCandies.
3. Compare this potential maximum for each child to the pre-determined original highest number of candies.
4. If the total (current candies + extraCandies) for a child is greater than or equal to the highest number pre-determined, then for that child, return true in the corresponding index in the result array; otherwise, return false.

• To illustrate with examples:
  • For a child with 3 candies and 3 extraCandies, if the highest candies any child has initially is 5, then the new total for this child would be 6. Since 6 is more than 5, the result would be true for this child.
  • Conversely, if a child has only 1 candy and the highest is 10, even with 3 extraCandies, they would only reach 4, making the result false.

This approach ensures that we can efficiently determine the possibilities for each child in a single pass through the list, after establishing the max reference point.

Solutions

class Solution {
public:
    vector<bool> canHaveMostCandies(vector<int>& candies, int extra) {
        int maximumCandies = *max_element(candies.begin(), candies.end());
        vector<bool> output;
        for (int item : candies) {
            output.push_back(item + extra >= maximumCandies);
        }
    
        return output;
    }
};