268. Missing Number

268

EasyBit ManipulationBit manipulation with XORXOR of indices and values

Missing Number

Given an array nums containing n distinct numbers drawn from the range [0, n], return the single number in that range that is missing from the array.

Open official problem prompt ↗

In plain English

Identify the one value from 0..n that never shows up in an array of the other n values.

Picture it like this

A teacher calls the class roll from a list numbered 0 to n. Every student who answers gets checked off both on the roster and against a seat number; the one seat number that never gets a matching answer is the absent student.

Example

Input: nums = [3, 0, 1]
Output: 2
Why: n = 3, so the full range is [0, 3]; the array holds 0, 1, 3, leaving 2 missing.

Constraints

n == nums.length1 <= n <= 10^40 <= nums[i] <= nAll the numbers of nums are unique

Pattern lesson

See the pattern, then code

XOR of indices and values

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. If you XOR together all indices 0..n and all array values, every number that is present appears exactly twice (once as an index, once as a value) and cancels, leaving only the missing number that appeared solely as an index.

New words, made simpleKnow these before the algorithm

XOR (^): Cancels equal operands: x ^ x = 0, and x ^ 0 = x.
Index-value pairing: Treating positions 0..n and stored values as one combined multiset.
Overflow-free: XOR avoids the integer-overflow risk that the sum formula can hit in fixed-width languages.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort and scan

Correct but slower than linear and mutates or copies input.

Sort nums, then look for the first index whose value does not match.

Time O(n log n)Space O(1)

Gauss sum

Fine in Python; in fixed-width languages the sum can overflow.

Subtract the array sum from n(n+1)/2.

Time O(n)Space O(1)

Best choiceXOR indices with values

Linear, constant space, and overflow-proof.

XOR all of 0..n and all values; present numbers cancel in pairs.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing the first k elements, res equals the XOR of {0..n} together with the k values seen so far, so any number appearing as both an index and a value has already cancelled.

Why this is correct

Reasoning

The combined multiset is {0,1,...,n} plus the n array values. Every number except the missing one appears exactly twice (once from the index range, once from the array) and XORs to 0. The missing number appears only once, as an index, so it survives.

The algorithm in three movesSay these aloud before coding

1Seed the result with n (the largest index, which has no matching array slot)

res = 3 (seed with n)

2Walk the array, XOR-ing in each index i and each value nums[i]

i=0: res ^= 0 ^ 3 -> 0

3The surviving value is the missing number

i=1: res ^= 1 ^ 0 -> 1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readn = 3

2 · AskWhat index has no array slot?

3 · Update stateres = 3

4 · ResultStart with the top index

Key takeaway

Every present number cancels against its matching index; only the missing 2 remains.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Seed with n
Indices only naturally run 0..n-1, so pre-loading n adds the one index the loop cannot reach.
2
Lines 4-5Fold index XOR value
Each iteration cancels a present number against its own index; the missing number never gets cancelled.
3
Lines 6Return the survivor
The lone uncancelled value is exactly the missing number.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Missing number is 0 (e.g. nums = [1])
Missing number is n itself (e.g. nums = [0, 1, 2] with n = 3)
Single-element array like [0] returns 1

Common beginner mistakes

Forgetting to seed with n, which drops the top index from the XOR
Reaching for the sum formula and hitting overflow in fixed-width languages
Assuming the array is sorted — it is not guaranteed

Check your understanding

How does seeding res with len(nums) handle the case where n itself is missing?

Missing Number

Missing Number

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation