Module 25 · Bit Manipulation, Mathematics, and Designed Data Structures

242. Missing Number with XOR

Foundation · Download this solution · All solutions and shared helpers

Problem

Given a length-n list of distinct integers drawn from 0 through n inclusive, return the one missing value. Empty input returns zero. The values satisfy the stated range and uniqueness guarantees. Do not mutate or sort the input.

Examples

Example 1

missing_number([3,0,1])
=> 2

The missing interior range value remains after cancellation.

Example 2

missing_number([0,1])
=> 2

The omitted value may be the upper endpoint n.

Example 3

missing_number([])
=> 0

The expected range contains only zero.

Reveal the worked solution and reasoning

Why this mechanism works

XOR the complete expected range and the actual values. Every present value occurs once on each side and cancels. Use the loop's index to supply expected values 0 through n-1, and seed the accumulator with n to include the final expected value.

State and boundaries

After processing index i, answer contains n XOR all expected indices through i XOR all actual values through i.

Protocol

Initialize answer to len(nums).
For each index and value XOR both into answer.
Return the unmatched expected value.

Visualization

actual [3,0,1]; expected 0,1,2,3
cancel 0,1,3 on both sides
unmatched expected value 2 remains

Python implementation

def missing_number(nums):
    answer = len(nums)
    for i, value in enumerate(nums):
        answer ^= i ^ value
    return answer

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

missing_number([3,0,1])

L2 missing_number: answer = len(nums)
nums=[3, 0, 1]; answer=3

L3 missing_number: for i, value in enumerate(nums):
nums=[3, 0, 1]; answer=3; i=0; value=3

L4 missing_number: answer ^= i ^ value
nums=[3, 0, 1]; answer=0; i=0; value=3

L3 missing_number: for i, value in enumerate(nums):
nums=[3, 0, 1]; answer=0; i=1; value=0

L4 missing_number: answer ^= i ^ value
nums=[3, 0, 1]; answer=1; i=1; value=0

L3 missing_number: for i, value in enumerate(nums):
nums=[3, 0, 1]; answer=1; i=2; value=1

L4 missing_number: answer ^= i ^ value
nums=[3, 0, 1]; answer=2; i=2; value=1

Result: 2. The missing interior range value remains after cancellation.

missing_number([0,1])

L2 missing_number: answer = len(nums)
nums=[0, 1]; answer=2

L3 missing_number: for i, value in enumerate(nums):
nums=[0, 1]; answer=2; i=0; value=0

L3 missing_number: for i, value in enumerate(nums):
nums=[0, 1]; answer=2; i=1; value=1

Result: 2. The omitted value may be the upper endpoint n.

Why the solution is correct

At completion, the expected terms cover 0..n exactly once. All actual terms are distinct members of that range, so every present number cancels with its expected term. The only remaining term is the missing number, including zero when the input is empty.

Time and space

O(n) XOR operations and O(1) integer variables; indices require O(log(n+1)) bits.

Common mistakes

Starting at zero without also XORing n omits one expected value. Duplicate or out-of-range inputs invalidate cancellation's interpretation.

Reasoning card

State: After processing index i, answer contains n XOR all expected indices through i XOR all actual values through i.

Invariant: Paired values cancel, leaving the missing one.

Decision to rehearse: XOR all expected indices and actual values.

Finish: Return the unmatched expected value

Transfer exercise

Compare the XOR method with n*(n+1)//2-sum(nums), discussing fixed-width overflow versus Python's arbitrary-precision arithmetic.