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)$


Comment