Reference: LeetCode EPI 11.10
Difficulty: Easy

My Post: [Super Java Collection] Brute-Force, HashMap+Count, HashSet+Math, Bitwise (clever), Sorting

Problem

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Note:

  • The given array size will in the range [2, 10000].
  • The given array’s numbers won’t have any order.

Example: 

1
2
Input: nums = [1,2,2,4]
Output: [2,3]

Analysis

Brute-Force

For each value from 1 to n, count its occurrence in nums.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[] findErrorNums(int[] nums) {
  // assume nums is non-empty
  int n = nums.length;
  int dup = -1, miss = -1;

  for (int i = 1; i <= n; ++i) { // for 1...n
    int count = 0;
    for (int val : nums) {
      if (val == i) {
        count += 1;
      }
    }
    if (count == 2) dup = i;
    if (count == 0) miss = i;
    // if both are set, then break
    if (dup > 0 && miss > 0) break;
  }

  return new int[] { dup, miss };
}

Time: $O(N^2)$
Space: $O(1)$

Map + Count

Note: Break the loop when dup and miss are all set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] findErrorNums(int[] nums) {
  // assume nums is non-empty
  int n = nums.length;
  Map<Integer, Integer> map = new HashMap<>();
  // first pass - count
  for (int val : nums) {
    map.put(val, map.getOrDefault(val, 0) + 1);
  }
  // second pass
  int dup = -1, miss = -1;
  for (int i = 1; i <= n; ++i) {
    if (map.containsKey(i) == false) miss = i;
    else if (map.get(i) == 2) dup = i;
    // if both are set, then break
    if (dup > 0  && miss > 0) break;
  }
  return new int[] { dup, miss };
}

Time: $O(N)$
Space: $O(N)$

Set + Math

See the example for how this method works.

1
2
// actual:   1 + 2 + 4 = 7 (use a hash set to remove extra duplicates)
// expected: 1 + 2 + 3 + 4 = 10

So expected - actual = miss. And dup can be detected in the array iteration.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] findErrorNums(int[] nums) {
  // assume nums is non-empty
  int n = nums.length;
  Set<Integer> set = new HashSet<>();

  int actualSum = 0;
  int dup = 0;
  for (int val : nums) {
    if (!set.contains(val)) {
      actualSum += val;
    } else {
      dup = val;
    }
    set.add(val);
  }
  
  // math
  int expectedSum = (1 + n) * n / 2;
  int miss = expectedSum - actualSum;
  
  return new int[] { dup, miss };
}

Bit Manipulation (XOR)

No Extra Space!

The idea is very clear. I should use an example to explain it.

1
2
// 1  2  3  4  5 (expected)
// 1  2  2  4  5 (actual)

Note: XOR: x ^ x = 0, x ^ y ^ x = y, x ^ y ^ x ^ x ^ y = x (remember this usage!)

First Pass: By doing XOR for each number above, xor would finally equals 2^3, which is miss^dup; however, we don’t know which is which!

Second Pass:

  • Then we use xor & ~(xor - 1) to get the rightmost one-bit of xor. For example, if xor in binary is 00011010, the result is 00000010. We call it oneBit.
  • Again, for each number above, if a number has that bit on, we put it to a set group; otherwise, throw it to unset group.
1
2
3
4
5
6
7
// 1  2  3  4  5
// 1  2  2  4  5
//
//    set: 1  1  2  2  2
//  unset: 3  4  4  5  5
//
// notice that I don't actually examine their binary form, just for demonstration
  • By doing XOR for set and unset groups, we would have setXor = 2 and unsetXor = 3; however, we don’t know which is which! T_T

Third Pass: Decide which is which :)

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
30
31
32
33
34
35
36
37
38
39
40
41
public int[] findErrorNums(int[] nums) {
  // assume nums is non-empty
  int n = nums.length;

  // first pass
  int xor = 0;
  for (int i = 1; i <= n; ++i) {
    xor ^= (i ^ nums[i - 1]);
  }
  
  // second pass
  int oneBit = xor & ~(xor - 1);
  int setXor = 0, unsetXor = 0;
  for (int i = 1; i <= n; ++i) {
    // for i
    if ((i & oneBit) > 0) {
      setXor ^= i;
    } else {
      unsetXor ^= i;
    }
    // for nums[i - 1]
    if ((nums[i - 1] & oneBit) > 0) {
      setXor ^= nums[i - 1];
    } else {
      unsetXor ^= nums[i - 1];
    }
  }

  // third pass
  int dup = setXor;
  int miss = unsetXor;
  for (int val : nums) {
    if (miss == val) { // miss should be the duplicate
      dup = unsetXor;
      miss = setXor; // exchange
      break;
    }
  }

  return new int[] { dup, miss };
}

Time: $O(N)$
Space: $O(1)$

Sorting

Not Recommended!

Check for corner cases: [1, 1], [2, 2], [1, 2, 2], [2, 2, 3]. We can reduce the corner case logic of miss to checking the first element and last element in the array.

  • If the first element after sorting is not 1, then 1 is the missing element.
  • If the last element after sorting is not n, then n is the missing element.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] findErrorNums(int[] nums) {
  int n = nums.length;
  Arrays.sort(nums);
  int dup = -1, missing = -1;
  if (n == 2) {
    return (nums[0] == 1) ? new int[] { 1, 2 } : new int[] { 2, 1 };
  }
  for (int i = 0; i < n - 1; ++i) {
    int curr = nums[i], next = nums[i + 1];
    if (curr == next) dup = curr;
    else if (curr + 1 < next) missing = curr + 1;
  }
  // checking corner cases
  if (nums[0] != 1) missing = 1;
  if (nums[n - 1] != n) missing = n;
  return new int[] { dup, missing };
}

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