4.30.5 — Missing Number

LeetCode 268 · Easy · ★ Blind 75

The problem

An array holds n distinct numbers taken from the range 0 to n. Exactly one is missing. Find it.

[3,0,1]           →  2
[9,6,4,2,3,5,7,0,1]  →  8
[0]               →  1

The follow-up asks for O(n) time and O(1) extra space.

Three solutions

All three are O(n); the difference is space and overflow behaviour.

Sorting is O(n \log n) and immediately out.

A hash set is O(n) time and O(n) space — fails the follow-up.

Two real answers remain.

Solution 1 — the sum formula

The numbers 0 to n sum to a known value, thanks to Gauss:

0 + 1 + \cdots + n = \frac{n(n+1)}{2}

Subtract the actual sum and the difference is the missing number.

n = len(nums)
return n * (n + 1) // 2 - sum(nums)

One line, and easy to explain.

The catch is overflow. For very large n, the expected sum can exceed a fixed-width integer even when the answer does not. In Python integers are unbounded, so it cannot happen; in Java or C++ it can, and the standard fix is to subtract as you go rather than computing both totals first:

missing = n
for i, x in enumerate(nums):
    missing += i - x
return missing

That keeps every intermediate value small, and it is what you would write in a fixed-width language.

Solution 2 — XOR

XOR every index together with every value.

Each number from 0 to n appears twice — once as an index and once as a value — except the missing one, which appears only as an index. Every pair cancels, and the missing number survives.

No overflow is possible, because XOR never produces a bit outside the range of its inputs. That is its advantage over the sum formula, and it is the reason to prefer it.

The solution

Python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)                    # the index n has no array slot

        for i, x in enumerate(nums):
            result ^= i ^ x

        return result

TypeScript

function missingNumber(nums: number[]): number {
  let result = nums.length;

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

  return result;
}

result starts at len(nums), which is n. The indices only run from 0 to n−1, so n itself would never be XOR-ed in otherwise — and n is a legitimate candidate for the missing number, as [0] shows.

result ^= i ^ x folds both the index and the value in on each iteration.

Trace

[3, 0, 1], so n = 3.

Start at 3. Then XOR in 0^3, 1^0, 2^1.

Everything together: 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1. Reorder: (3^3) ^ (0^0) ^ (1^1) ^ 2 = 2 ✓.

The reordering is legal because XOR is commutative — which is why the array's order never matters.

Complexity

O(n) time, O(1) space, for both real solutions.

Which to write

Say the sum formula first — it is the most natural and easiest to explain — then mention that XOR avoids overflow entirely. Offering both plus the trade is a better answer than either alone.

Where this goes next

• Single Number — XOR cancelling pairs, the same property. 4.30.1.
• Find All Numbers Disappeared in an Array — several missing, so XOR cannot separate them. Mark visited by negating nums[abs(x) - 1], then report the indices still positive. A good demonstration of when XOR stops working.
• Find the Duplicate Number — one duplicate, no mutation, no extra space. XOR does not help; it becomes cycle detection. 4.9.8.
• Set Mismatch — one number duplicated and one missing. Both the sum and XOR approaches extend, and the XOR version needs the partition-by-a-differing-bit trick from 4.30.1.

The pattern across all of these: when values and indices come from the same range, pair them off and see what survives.

What the interviewer will push on

"Why does XOR work here?" Every number appears twice — once as an index, once as a value — except the missing one.

"Why start at n?" The indices stop at n−1, so n must be introduced by hand.

"Why prefer XOR over the sum?" No overflow. Then note that Python makes the point moot but the habit is right.

"What if several numbers were missing?" XOR cannot separate them. Use the negation-marking trick or a set.

"What is the sum formula?" n(n+1)/2, and say Gauss's name if you like the story.

One thing to volunteer: give both solutions and the overflow trade in one breath. This is an easy problem, and the way to stand out on it is to show you thought about the failure mode rather than just the answer.

Next: 4.30.6 Sum of Two Integers — addition without +, and the Python trap that makes it genuinely awkward.