Last Updated: 26 May, 2022

Candy Distribution

Moderate

Asked in companies

Solve now

Problem statement

You are given an integer ‘N’ and an array ‘A’ of size ‘N’ containing positive integers.

You have ‘N’ friends, and you want to give each of them some candies. The ‘ith’ friend will be happy if they receive at least ‘A[i]’ candies. You want to distribute candies among your friends to fulfill the following two conditions.

No two friends have the same number of candies.

Every friend is happy.

Your task is to find the minimum candies required for distributing such that both conditions are met. If no distribution fulfills both given conditions, report it.

Example :

‘N’ = 5, ‘A’ = [3, 3, 2, 5, 1]
If we distribute candies in the following manner [4, 3, 2, 5, 1],
Each friend will be happy as they have at least received ‘A[i]’ candies, and no two friends got the same number of candies.
Hence, the answer is (4 + 3 + 2 + 5 + 1) = 15. It’s guaranteed that this is the minimum number of candies required.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains an integer, ‘N'.
The second line of each test case contains N single space-separated integers, representing array ‘A’.

Output Format :

For each test case, return the minimum number of candies required such that distribution follows both given conditions or return -1 if there is no such distribution.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^9
It’s guaranteed that sum of N over all test cases does not exceed 10^5.

Time limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

‘A[i]’ is the requirement of ‘ith’ friend.
Let’s say the requirements of all friends are unique, then we will give each friend candies equal to ‘A[i]’, and this will be the minimum candies required.
Now, let’s say two friends have an ‘A[i]’ requirement, then we can give the first friend ‘A[i]’ candies, and the second friend can receive ‘A[i] + 1’ candies to satisfy the condition.
So, we can sort requirements in non-decreasing order, and we will keep a variable ‘PREV’ to track the candies given to the last friend.
Initialize ‘PREV’ to 0.
Declare ‘ANS’ and assign it to 0 to store the number of candies given.
Iterate all friend's requirement ‘i’ from [0, ‘N’ - 1].
‘A[i]’ > ‘PREV’; then give ‘A[i]’ candies to this friend and assign ‘A[i]’ to ‘PREV’.
‘A[i]’ <= ‘PREV’; then give ‘PREV+1’ candies to this friend and increment ‘PREV’ by 1.
Add ‘PREV’ to ‘ANS’, as it is the number of candies given to ‘ith’ friend.
Return ‘ANS’ after giving candies to each friend.
Note: -1 will never be the answer because we can always distribute candies to friends; the real problem was to find the minimum candies required.

Algorithm:

Sort the given array ‘a’ in non-decreasing order.
Declare two-variable ‘ans’ and ‘prev’ and assign them to 0.
Iterate over to the element of ‘a’ from [0,'n' - 1]:
If ‘a[i]’ > ‘prev’ then ‘prev’ = ‘a[i]’.
else ‘prev’ = ‘prev + 1’.
So it means we have given ‘prev’ candies to ‘ith’ friend, so add ‘prev’ to ‘ans’.
Return ‘ans’ after the loop.

Solve now