Find the Missing ID (Sum, XOR and Their Trade-Offs)

Pattern: Hashing, Stacks and Bit Tricks (Must-Know Classics) · Difficulty: Easy · Asked at: Amazon, Microsoft, Apple

Classic version: LeetCode 268

Problem

A batch should contain every sequence number from 0 to n exactly once, but one is missing. ids holds the n numbers received, in any order. Return the missing one in O(n) time and O(1) extra space.

Examples

missing_id([3, 0, 1])                    → 2
missing_id([0, 1])                       → 2
missing_id([9, 6, 4, 2, 3, 5, 7, 0, 1])  → 8

Starter code

def missing_id(ids: list[int]) -> int:
    pass

Hints

Where this shows up in data engineering

Gap detection in sequence numbers is a real data quality check: missing Kafka offsets, dropped CDC log sequence numbers, missing daily partitions. At scale you’d use LAG() to find gaps (several may be missing), but the O(1)-memory sum/XOR checksum idea is exactly how reconciliation jobs compare counts and checksums between source and target without moving the data.

Solution

def missing_id(ids: list[int]) -> int:
    n = len(ids)
    missing = n                      # start with n, then XOR every index and value
    for i, x in enumerate(ids):
        missing ^= i ^ x
    return missing

Tests

Your solution should pass these:

assert missing_id([3, 0, 1]) == 2
assert missing_id([0, 1]) == 2
assert missing_id([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
assert missing_id([1]) == 0
assert missing_id([0]) == 1

Explanation

Sum: n(n+1)/2 - sum(ids). One line, O(n), O(1). In fixed-width languages the sum can overflow; Python ints can’t.

XOR: every present value cancels with its matching index; the missing value has no partner and survives. No overflow risk, same complexity.

Set difference / sorting: O(n) space or O(n log n) time. Fine as first answers.

Two numbers missing? Sum and sum of squares give two equations; or XOR everything to get a ^ b, split numbers by any set bit of that, and XOR each group.

Follow-up questions