Make all elements of the array distinct.

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
5 upvotes
Asked in companies
eBayUberWalmart

Problem statement

You have been given an array/list ‘ARR’ of integers consisting of ‘N’ integers. In one operation you can increase an element by 1. Your task is to return the minimum number of operations to make the array distinct.

Example: 
Let’s say you have an array/list [1,4,4,5]. We can increase the third element by 1 and the fourth element by 1. Finally, our array will look like [1,4,5,6] where all elements are distinct. Therefore the minimum number of operations is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of the array/list ‘ARR’.

The second line and the last line of input contain ‘N’ single space-separated integers representing the array/list elements.
Output Format: 
For each test case, return the minimum number of operations to make the array distinct.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
1 <= ‘ARR[i]’ <= 10^4  

Time Limit: 1 sec
Sample Input 1:
2
4
2 2 4 4  
4 
7 1 1 1
Sample Output 1:
2
3

Sample Output 1 Explanation:

Test case 1:

We can increase the first and fourth elements by 1 in the array/list. The array/list will become [3,2,4,5] where all elements are distinct.

Therefore the answer is 2.

Test case 2:

We can increase the second element twice and the fourth element once in the array/list. The array/list will become [7,3,1,2] where all elements are distinct.

Therefore the answer is 3.
Sample Input 2:
2
4
1 2 6 4
8
1 2 3 4 4 3 2 1
Sample Output 2:
0
16
Hint

Maintain count of each element present in the array.

Approaches (2)
Maintaining Count of Each Element.

We will maintain the count of each element present in an auxiliary array. Finally, each element must have at most one occurrence.

We will apply the algorithm as follows:-

 

  • Declare an array/list ‘COUNT’ to store the count of each element initially initialized with zero.Its size must be ‘N+max(ARR[i])’. Because in the worst case all elements are equal. Therefore after making all elements distinct maximum element will be ‘N+max(ARR[i])-1’
  • Iterate through the array ‘arr’ and increase ‘COUNT[ARR[i]]’ by 1.
  • Declare ‘ANS’ and initialize it with zero.
  • We will iterate ‘COUNT’:-
    • If ‘COUNT[i]’ <= 1 no update is required as the element is distinct and has at most one occurrence.
    • If ‘COUNT[i]’ > 1 we need to apply the operation on ‘COUNT[i]-1’ occurrences of ‘i’ because only one occurrence of ‘i’ is possible. Therefore increase ‘ANS’ by ‘COUNT[i]-1’. After applying ‘COUNT[i]-1’ operations no of occurrences of i+1 increases by ‘COUNT[i]-1’ and ‘COUNT[i]’ becomes 1.
  • Return ‘ANS’.
Time Complexity

O(N + max(ARR[i])), where ‘N’ denotes the size of array/list and ‘max(ARR[i])’ denotes maximum element in array/list ‘ARR’.

 

For an array/list of size ‘N’, we will have to iterate an auxiliary array of size ‘N+max(ARR[i])’.

Space Complexity

O(N + max(ARR[i])’), where ‘N’ denotes the size of array/list and ‘max(ARR[i])’ denotes maximum element in array/list ‘ARR’.

 

We build an auxiliary array/list to store the count of each element in ‘ARR[i]’.

Code Solution
(100% EXP penalty)
Make all elements of the array distinct.
Full screen
Console