Make all elements of the array distinct.
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

Question

Make all elements of the array distinct.

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

Accepted Answer

Steps:
1) The idea is to sort the input , then we move forward from the beginning of the array till the end.
2) As soon as we found a condition that the current element is less than or equal to the previous elements then we need to update the current array element by adding 1 to its prev element .
3) At the same time we need to keep track of result by result += A[i-1]- A[i]+1;

Accepted Answer

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’.

Space Complexity: OtherExplanation:

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]’.

Time Complexity: OtherExplanation:

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])’.

Python (3.5)

'''

    Time Complexity: O( 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'.    

'''



def makeArrayUnique(arr,  n):

    

    count = [0] * (10001 + n)

    

    for i in range(n):

        count[arr[i]] += 1

    

    ans=0

    

    for i in range(len(count)):

        if (count[i] > 1):

            ans += count[i] - 1

            count[i + 1] += count[i] - 1

            count[i] = 1



    return ans

Java (SE 1.8)

/*
    Time Complexity: O( 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'.
*/
    
import java.util.ArrayList;

public class Solution {
    public static int makeArrayUnique(ArrayList < Integer > arr, int n) {
        int[] count = new int[10001 + n];

        for (int i = 0; i < n; i++) {
            count[arr.get(i)]++;
        }

        int ans = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 1) {
                ans += count[i] - 1;
                count[i + 1] += count[i] - 1;
                count[i] = 1;
            }
        }

        return ans;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O( 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'.
*/

int makeArrayUnique(vector < int > & arr, int n) {
    vector < int > count(10001 + n, 0);

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    int ans = 0;
    for (int i = 0; i < count.size(); i++) {
        if (count[i] > 1) {
            ans += count[i] - 1;
            count[i + 1] += count[i] - 1;
            count[i] = 1;
        }
    }

    return ans;
}

Accepted Answer

Sorting

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’.

Space Complexity: O(1)Explanation:

O(1),

AS we used only constant space.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)’), where ‘N’ denotes the size of array/list.

We are sorting array/list of integers once.