Missing Number

The problem

Array nums contains n distinct numbers in [0, n]. Exactly one number in that range is missing. Return it.

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

Input:  [0,1]
Output: 2

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

Brute force

Sort and scan for gap, or use a set and probe 0..n.

function missingNumberBrute(nums: number[]): number {
  const set = new Set(nums);
  for (let i = 0; i <= nums.length; i++) {
    if (!set.has(i)) return i;
  }
  return -1;
}

Time	O(n)
Space	O(n)

Optimal A: XOR

i ^ nums[i] for all i, plus n. Missing value remains (pairs cancel).

function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) {
    x ^= i ^ nums[i];
  }
  return x;
}

Optimal B: math sum

function missingNumberSum(nums: number[]): number {
  const n = nums.length;
  const expected = (n * (n + 1)) / 2;
  const actual = nums.reduce((a, b) => a + b, 0);
  return expected - actual;
}

In languages with fixed ints, sum can overflow; XOR does not. JS numbers are fine for interview constraints.

Time	O(n)
Space	O(1)

Edge cases

• Missing 0
• Missing n
• n = 1 → [0] missing 1 or [1] missing 0

Common bugs

• Looping only to n-1 and forgetting to XOR n
• Integer division mistakes in other languages
• Sorting then claiming O(n)

Interview delivery

1. Range 0..n, one missing.
2. Prefer XOR or Gauss.
3. Code clean O(1) space.
4. Call out overflow in fixed-width ints.

Related

• Number of 1 Bits
• Reverse Bits
• Sum of Two Integers
• Find Duplicate Number

Why XOR pairs cancel

0^1^…^n xor’d with every array element leaves the missing value because each present number appears twice (once from the range, once from the array) and x^x = 0. The missing appears once.

Sum method precision talk

In JS, numbers are IEEE doubles — integers stay exact up to 2^53. For interview constraints (n ≤ 10^4 or even 10^5), Gauss sum is fine. In Java int, prefer long or XOR.

Sort alternative (mention only)

Sort O(n log n), then scan for nums[i] != i. Correct but slower and mutates input. Use only if they forbid bit tricks and extra O(n) structures.

Follow-ups

• Find the duplicate when range is 1..n with one duplicate (Floyd cycle).
• Find missing and duplicate together.
• Missing number in a stream.

Further reading

• LeetCode 268 — Missing Number
• Bitwise XOR