Why does XOR find the missing number?

XOR cancels equal values (x ^ x = 0) and leaves others unchanged (x ^ 0 = x), in any order. Every number from 0 to n is XORed in twice, once as an index or as n and once as a value, except the missing one, which appears only once and is all that remains.

Is the sum formula just as good?

n(n + 1) / 2 minus the sum of the array also gives the answer in O(n) time and O(1) space. XOR has no overflow risk in fixed-width integers, which is why interviewers often ask for it as the follow-up.

Why start with missing = n?

The indices run from 0 to n - 1, but the numbers run from 0 to n. Starting with n adds the one number that no index covers.

Missing Number

Find the one number missing from 0..n in O(n) time and O(1) space by XORing every index and value so the pairs cancel.

EasySolve on LeetCode

Problem Understanding

Missing Number: an array nums holds n distinct numbers taken from 0, 1, …, n. Exactly one number in that range is missing. Return it, ideally in O(n) time with O(1) extra space.

Example: nums = [3, 0, 1] has n = 3, so the range is 0..3, and 2 is missing.

Attempt 1: A Set or Sorting

Put every number in a hash set, then check 0..n for the one that is absent: O(n) time but O(n) extra space. Sorting and looking for the first nums[i] != i uses no extra set but costs O(n log n) time. XOR gets both O(n) time and O(1) space.

The Intuition: Pairs Cancel Under XOR

Two facts about XOR do all the work:

x ^ x = 0: a number XORed with itself cancels.
XOR is order-independent, so the pairs do not need to be next to each other.

XOR together every index 0..n-1, the number n, and every value in nums. Each number that is present appears twice (once as an index or n, once as a value) and cancels. The missing number appears only once, so it is exactly what is left.

Interactive Walkthrough

The top row is nums; the bottom row is every number 0..n, filled while it has been XORed in an odd number of times. Each step XORs in one index and one value, so pairs switch off, and at the end exactly one number is still on: the missing one.

Dry Run Table

Input: nums = [3, 0, 1], so n = 3

Step	XOR in	`missing`
start	`n = 3`	3
i = 0	`0 ^ 3`	3 ^ 0 ^ 3 = 0
i = 1	`1 ^ 0`	0 ^ 1 ^ 0 = 1
i = 2	`2 ^ 1`	1 ^ 2 ^ 1 = 2

The answer is 2.

The Solution Template

XOR every index and every value into a running result that starts at n.

Missing Number Code

1var missingNumber = function(nums) {
2    let missing = nums.length;
3    for (let i = 0; i < nums.length; i++) {
4        missing ^= i ^ nums[i];
5    }
6    return missing;
7};

Edge Cases & Common Mistakes

n itself is missing: [0, 1] returns 2; starting with missing = n covers this case.
0 is missing: [1] returns 0.
Starting with missing = 0: then n is never XORed in and the answer is wrong whenever n is present.
Sum formula overflow: n(n + 1) / 2 can overflow 32-bit integers for large n; XOR cannot.

Summary

XOR every index, n, and every value: each present number cancels with its partner, and the missing number is the only thing left. O(n) time, O(1) space, no overflow.

More practice: DSA interview questions with answers · patterns cheat sheet

Single Number

Reverse Bits