Missing number: XOR cancellation over values and indices

Coding Challenges
, ,
1

Problem. Given n distinct numbers from the range 0..n, find the single missing value.

This is the classic XOR parity trick pattern.

Examples:

  • nums = [3, 0, 1] → 2
  • nums = [0, 1] → 2
  • nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8

Solution. XOR all indices and all values together. Every value that appears in both places cancels out, leaving only the missing number.

def missing_number(nums):
    missing = len(nums)
    for index, value in enumerate(nums):
        missing ^= index
        missing ^= value
    return missing

O(n) time, O(1) space.

Gotchas.

  • The arithmetic-sum approach also works, but XOR avoids overflow in fixed-width languages.
  • Initialize with len(nums) so the final range value n participates in the cancellation.
  • This relies on exactly one missing value and no duplicates.

Run: Missing Number