Candy Distribution

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
SprinklrIntuit

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
5 9 10
4
12 10 1 1
Sample Output 1 :
24
25
Explanation For Sample Input 1 :
For test case 1: 
We can give each friend exactly the number of candy they require, so we will distribute candy as follow: [5, 9, 10], total candies will be 24.
Hence, the answer will be 24.

For test case 2:
The following distribution will give the optimal answer:
[12, 10, 2, 1], total candies will be 25.
Hence, the answer will be 25.
Sample Input 2 :
2
5
3 5 5 1 1
2
7 8
Sample Output 2 :
17
15
Hint

If the requirement of all friends is unique, how will you distribute candies?

Approaches (1)
Sorting

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.
Time Complexity

O(NlogN), here ‘N’ is the number of friends.

Sorting takes O(NlogN) time. Everything else is just linear.

Hence, the time complexity is O(NlogN).

Space Complexity

O(N), here ‘N’ is the number of friends.
We are not using any extra space. Only the provided array takes O(N) space.

Code Solution
(100% EXP penalty)
Candy Distribution
Full screen
Console