Reference: LeetCode
Difficulty: Easy

My Post: [Java] Summary of All Solutions Except Sorting! (also handle overflow)

Problem

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example: 

1
2
3
4
5
Input: [3,0,1]
Output: 2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Analysis

Brute-Force

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

Hash Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int missingNumber(int[] nums) {
  int n = nums.length;
  Set<Integer> set = new HashSet<>();
  // first pass
  for (int val : nums) {
    set.add(val);
  }
  // second pass
  for (int i = 0; i <= n; ++i) {
    if (set.contains(i) == false) {
      return i;
    }
  }
  throw new IllegalArgumentException();
}

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

Bit Manipulation

It is based on the fact that x ^ x = 0. 

1
2
3
4
5
6
7
8
9
10
11
// 0 ^ 0 = 0
public int missingNumber(int[] nums) {
  int n = nums.length;
  int xor = 0;
  for (int i = 0; i < n; ++i) {
    int val = i + 1;
    xor ^= (val ^ nums[i]);
  }
  // xor ^= n; // the number n
  return xor;
}

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

Math (Gauss’ Formula)

Formula: $1 + 2 + 3 + 4 + \ldots + n = \frac{n(n + 1)}{2}$

1
2
3
4
5
6
7
8
9
10
11
12
13
// nums = [] --> missing 0
// nums = [0] --> missing 1
public int missingNumber(int[] nums) {
  // assume nums is not null
  // consider case when n = 0 --> return 0
  int n = nums.length;
  int expectedSum = (1 + n) * n / 2;
  int actualSum = 0;
  for (int i = 0; i < n; ++i) {
    actualSum += nums[i];
  }
  return expectedSum - actualSum;
}

Improvement: It can handle overflow.

1
2
3
4
5
6
7
8
public int missingNumber(int[] nums) {
  int n = nums.length;
  int result = 0;
  for (int i = 0; i < n; ++i) {
    result += (i + 1) - nums[i];
  }
  return result;
}

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