Fewest Increments to Make Every Value Unique
Hudson River Trading● MediumFULLTIMEOAProblem statement
You are given an integer array nums. In one move, you pick any index i and increase nums[i] by 1.
Return the fewest moves needed so that all values in nums are different.
A value may go above 10^9 while you raise it. The answer can be larger than 2^31 - 1, so return it as a 64-bit integer.
Function
minIncrementsForUnique(nums: int[]) → longExamples
Example 1
nums = [1,1,2]return = 2Both 1s cannot stay. Raise the second 1 to 2 (1 move). Now the two 2s clash, so raise one of them to 3 (1 move).
The values become [1, 2, 3] after 2 moves. One move is not enough. Raising a 1 makes it clash with the 2, and raising the 2 leaves the two 1s.
Example 2
nums = [4,0,4,4,1]return = 3Sorted, the values are [0, 1, 4, 4, 4]. The 0, the 1 and one 4 keep their values. The other two 4s go to 5 (1 move) and 6 (2 moves).
The total is 1 + 2 = 3.
Example 3
nums = [3,8,5]return = 0All three values are already different, so no moves are needed.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^9