Last Updated: 25 Aug, 2021

Maximum Candies

Easy

Asked in companies

Solve now

Problem statement

You are given the array ‘children’ of size ‘N’ representing the number of candies present at each child. You have a ‘extraCandies’ amount of candies. Your task is to find for each child if the child has the most candies among all children if all ‘extraCandies’ are given to the child.

You have to return a boolean array. ‘True’ is present at position ‘index’ if the child at position ‘index’ will have the maximum amount of candies when given all the ‘extraCandies’ candies.

For example:

You are given ‘children’ = [12, 20, 5], and ‘extraCandies’ = ‘9’

If you give all the candies to the child at position 1, the child will have 21 candies, which is the highest among all children.

If you give all the candies to the child at position 2, the child will have 29 candies, which is the highest among all children.

If you give all the candies to the child at position 3, the child will have 14 candies, which is not the highest among all children.

Hence the answer is [True, True, False].

Input Format:

The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains two integers, ‘N’ and ‘extraCandies’, representing the number of children and extra candies.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements of the array ‘children’ where ‘children[index]’ represents the number of candies present at child at ‘index’ position.

Output Format:

For each test case, print an array of boolean values. ‘True’ is present at position ‘index’ if the child at position ‘index’ has the maximum number of candies among all children after receiving extra candies. Otherwise, ‘False’ is present.

Print a separate line for each test case.

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
2 <= N <= 10^6
1 <= children[i] <= 10^9
1 <= extraCandies <= 10^9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will create an empty array results. We will iterate through each child in the children array.

We will give the extraCandies amount of candies to the current child. The total amount of candies that the current child has would be equal to child + extraCandies.
We will check if the child has the maximum amount of candies among all children then we will insert True in the array results. Otherwise, we will insert False.

Algorithm:

Create an empty array results.
Iterate child through the children array.
- Set currentValue equal to the sum of child and extraCandies.
- Set Flag as True.
- Iterate index from 0 to N.
  - We will check If children[index] is greater than currentValue.
    - Set Flag as False.
    - Break out from the loop.
- Insert Flag in results.
Finally, return the array results.

Solve now

02 Approach

In this approach, we will try to find the maximum number of candies a child has, and then we add extraCandies to each child value, then for each, and we check if

If, after adding extraCandies the number of candies a child has is greater than the maximum number of candies, we insert True in the results array.
Otherwise, we will insert False in the results array.

Algorithm:

Set maxValue as -1.
Iterate child through the children array.
- Set maxValue as the maximum of maxValue and child.
Create an empty array results.
Iterate child through the children array.
- Set currentValue as the sum of child and extraCandies.
- If currentValue is less maxValue.
  - Insert False in results array.
- Otherwise,
  - Insert True in results array.
Finally, return the results array.

Solve now