Missing Number

Values come from 0 through n, with one missing. Return the missing value.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Missing Number: Initialize with n, then XOR every expected index and actual value so matched numbers cancel and the missing value survives.

Input and goalValues come from 0 through `n`, with one missing. Return the missing value.

Seed the unmatched endpointFor nums = [3, 0, 1], n = 3. Initialize missing = 3 because enumerate supplies expected indices 0, 1, and 2 but not endpoint 3.

next i=0300112

expectedDomain[0, 1, 2, 3]accumulatormissing = len(nums) = 3 = 0011₂

Recognize it

Values should contain every integer from 0 through n exactly once except one, making the actual multiset differ from the expected multiset by a single value.

Keep true

After processing indices before i, missing equals n XOR every processed expected index XOR every processed actual value. Equal values may be regrouped and cancel because XOR is associative, commutative, and self-inverse.

Reuse it

When all values occur in canceling pairs except one, XOR removes order and pair placement from the problem; the same invariant finds a unique element or separates parity-based membership differences.

Pattern: XOR cancellation.

Simple idea: XOR every expected index and every actual value. Matching values cancel, leaving only the missing value.

def missing_number(nums: list[int]) -> int:
   missing = len(nums)
   for index, num in enumerate(nums):
      missing ^= index ^ num
   return missing

Cost: $O(n)$ time and $O(1)$ space.