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


Comment