Missing Number

Examples

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

n = 3 (the list has 3 elements), so the full range is 0-3. Every value shows up except 2.

Input: nums = [0, 1]
Output: 2

n = 2, full range is 0-2. 0 and 1 are present, so 2 is missing.

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

n = 9, full range is 0-9. Every value is present except 8.

Constraints

• n == nums.length

• 1 <= n <= 10^4

• 0 <= nums[i] <= n

• All the numbers in nums are unique.

Approach

A direct way to find the missing number is to record every value that's actually present in a hash set, then check each number from 0 to n against that set until you find the one that's missing.

A cleverer approach uses XOR to avoid needing that extra set at all. Since the list is supposed to contain every number from 0 to n except one, imagine XORing together two things: every index from 0 to n (including the extra index n, since the list only has n indices from 0 to n-1 but the values range up to n), and every value actually present in the list. Every value that is present ends up paired with one of those indices and cancels itself out to 0 via XOR, no matter what order everything is combined in - leaving only the one number that never got a partner to cancel with: the missing one.

Solutions

Brute Force - Hash Set of Present Values

Put every value from the list into a hash set. Then check each number from 0 to n in order - the first one not found in the set is the missing number.

function missingNumber(nums) {
  const present = new Set(nums);
  const n = nums.length;

  for (let i = 0; i <= n; i++) {
    if (!present.has(i)) return i;
  }
}

Time: O(n) · Space: O(n)

Optimal - XOR Indexes and Values Together

XOR together every index from 0 to n, and every value actually in the list, into one running result (starting from n, to account for the extra index the list's length doesn't otherwise cover). Every present value cancels out with a matching index, leaving only the missing number.

function missingNumber(nums) {
  let result = nums.length; // accounts for index n, which has no array slot

  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }

  return result;
}

Time: O(n) · Space: O(1)