Missing Number

Sort and scan

Sort a copy of the values. In the complete sequence, position i should hold i, so the first mismatch is the missing number. If every stored value matches its position, the missing value is n itself.

def missing_number(nums: list[int]) -> int:
    ordered = sorted(nums)
    for expected, value in enumerate(ordered):
        if value != expected:
            return expected
    return len(nums)

Time O(n log n). Space O(n) for the sorted copy.

Index-value XOR

Exclusive OR (XOR) is a bitwise operation whose matching inputs cancel: value ^ value == 0. You can regroup and reorder XOR operations without changing the result.

Start the accumulator at n. Then XOR each index and each array value into it. Across the whole loop, the indices plus that initial n supply every number in 0..n. The array supplies every one of those numbers except the missing value. Every present value therefore appears twice and cancels.

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

Time O(n). Space O(1) — no sorting and no set proportional to the input.