Last Updated: 20 Mar, 2021
Make all elements of the array distinct.
Moderate
Asked in companies
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.
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
Approaches
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’.
We will sort the array/list ‘ARR’. As we can only apply the increment operation we just need to make the array/list increasing.
Following is the algorithm for this approach:
- Sort ‘ARR’.
- Declare ‘ANS’ and initialize it with zero.
- Declare ‘CURR_MAX’ and initialize it with zero. It stores maximum till the element we have iterated.
- We will iterate ‘ARR’:-
- If ‘ARR[i]’ > ‘CURR_MAX’ then it is first occurrence of ‘ARR[i]’ so no operation is required. We will just update ‘CURR_MAX’ to ‘ARR[i]’.
- If ‘ARR[i]’ <= ‘CURR_MAX’ then the updated value of one of the elements which have already been visited. We need to make it greater than ‘CURR_MAX’. Increase ‘ANS’ by ‘CURR_MAX’ + 1 - ‘ARR[i]’. Update value of ‘ARR[i]’ by ‘CURR_MAX’ + 1. Update ‘CURR_MAX’ to ‘ARR[i]’.
- Return ‘ANS’.