268. Missing Number

Missing Number looks like a counting problem, but it’s really an excuse to show off the one property that makes XOR magical: a value XOR’d against itself vanishes. That “self-cancellation” is the backbone of the whole bit manipulation pattern, and this is the cleanest place to see it earn its keep.

The problem

You get an array of n distinct numbers pulled from the range 0 to n inclusive — that’s n + 1 possible values but only n slots, so exactly one is left out. Return the one that’s missing. (Full statement on LeetCode.)

For [3, 0, 1] the range is 0..3, and 2 is the number that never shows up.

Intuition: XOR makes matched pairs disappear

Two facts about XOR do all the work here. First, x ^ x = 0 — any value cancels itself. Second, XOR is commutative and associative, so you can shuffle the operands into any order you like.

Now imagine two piles. One pile is every index the array should cover: 0, 1, …, n. The other is every value the array actually holds. Every number except the missing one appears in both piles, so if you XOR everything from both piles together, each of those doubled numbers annihilates its twin and drops to zero. The lone survivor is the value that appeared in the index pile but never in the value pile — the missing number.

$\Big(\bigoplus_{i=0}^{n} i\Big) \oplus \Big(\bigoplus_{k} \text{nums}[k]\Big) = \text{missing}$

The neat part is you don’t need two passes or a scratch array to build those piles. Seed an accumulator with n (the one index that has no matching array slot), then fold in each i ^ nums[i] as you walk the array once.

Solution

class Solution {
    public int missingNumber(int[] nums) {
        // Seed with n: it's the top of the 0..n range and has no array index.
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            // XOR the index and the value at that index into the running result.
            // Every number present in both cancels; the absent one remains.
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

If XOR isn’t the shape the interviewer wants, the arithmetic version reads more plainly. The sum of 0..n is fixed by Gauss’s formula, so subtract what’s actually there and the gap is the answer:

class Solution {
    public int missingNumberSum(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2;   // sum of 0..n
        int actual = 0;
        for (int num : nums) actual += num;
        return expected - actual;
    }
}

Both are one pass and constant space. The one caveat for the sum version: with a wider range you’d have to watch for integer overflow in expected, whereas XOR never overflows because it just flips bits. At this problem’s limits (n <= 10^4) int is safe either way.

Complexity

Approach	Time	Space
XOR	$O(n)$	$O(1)$
Gauss sum	$O(n)$	$O(1)$

In an interview

Reach for the sum approach first if you want to explain fast — everyone follows “expected total minus actual total.” Then offer XOR as the answer that sidesteps overflow entirely, which is a genuinely nice thing to say out loud because it shows you’re thinking past the given constraints. The trap to name before they ask: the sum formula quietly assumes the numbers are distinct: a duplicate would throw the count off and break both methods, so confirm that constraint up front.

The self-cancelling XOR idea threads through the rest of the bit manipulation pattern. It’s the same trick that lets Sum of Two Integers add without a +, and once you’re comfortable reading numbers bit by bit, Number of 1 Bits is the natural next stop.

References

• LeetCode 268 — Missing Number