The task is:
Given an array of integers, return the minimum required increment to make each element unique.
Sample Input 1: [3, 4, 2, 2, 6]
Sample Output 1: 3 (One of the 2s should be incremented to 5)
Sample Input 2: [3, 4, 5]
Sample Output 2: 0 (There is no duplicate)
My code works by shifting all numbers even if there is only one duplicate in a whole array. I guess this could be written more efficiently (e.g., in each duplicate, looking at the minimum number that does not exist in the array and shifting one of the duplicates to that number), but I couldn't manage it.
def getMinimumCoins(arr): sumBefore = sum(arr) arr.sort() previous = arr for i in range(1, len(arr)): if arr[i] <= previous: arr[i] = previous + 1 previous = arr[i] return sum(arr) - sumBefore
Besides, in the way I proposed above, decremental operations also could be possible. I mean, in my code, if the input is [3,3,3], the resulting array would be [3,4,5] with total increment equals 3. However, in the new algorithm, it could be possible to obtain a resulting array of [1,2,3] with a total decrement equals to -3.