Reference: LeetCode
Difficulty: Medium

Problem

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Note:

  • 0 <= A.length <= 40000
  • 0 <= A[i] < 40000

Example: 

1
2
3
4
5
6
7
Input: [1,2,2]
Output: 1
Exp: [1,2,3]

Input: [3,2,1,2,1,7]
Output: 6
Exp: [3,4,1,2,5,7]

Analysis

Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// [1,2,2]
// move: incrementing by 1
public int minIncrementForUnique(int[] A) {
  // Assume A is not null
  int n = A.length;
  if (n == 0 || n == 1) {
    return 0;
  }
  Arrays.sort(A); // sorting
  int moveNum = 0;
  for (int i = 0; i < n - 1; ++i) {
    if (A[i] >= A[i + 1]) { // duplicate and >= cases
      int diff = A[i] - A[i + 1];
      A[i + 1] += diff + 1;
      moveNum += diff + 1;
    }
  }
  return moveNum;
}

Time: $O(N\log{N})$
Space: $O(1)$

Variant: Unique Twitter User Id Set

Problem: Twitter | OA 2019 | Unique Twitter User Id Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static void main(String[] args) {
  // int[] arr = new int[0]; // covered in assumption

  // int[] arr = new int[] { 1 };         // 1
  // int[] arr = new int[] { 2,2,2,2 };   // 2,3,4,5
  // int[] arr = new int[] { 4,5,5 };     // 4,5,6 = 15
  int[] arr = new int[] { 3,2,1,2,7 }; // 17
  System.out.println(getUniqueUserIdSum(arr));
}

/** Returns the minimum */
public static int getUniqueUserIdSum(int[] arr) {
  // Assume arr is not null, and its size >= 1, <= 2000
  int n = arr.length;
  if (n == 1) {
    return arr[0];
  }
  Arrays.sort(arr); // sorting
  int minSum = 0;
  for (int i = 0; i < n - 1; ++i) {
    minSum += arr[i];
    if (arr[i] >= arr[i + 1]) { // duplicate & > cases
      int diff = arr[i] - arr[i + 1];
      arr[i + 1] += diff + 1;
    }
  }
  minSum += arr[n - 1]; // last element
  return minSum;
}

Time: $O(N\log{N$})$
Space: $O(1)$