Missing Number: Find the One Value Absent From 0 to n

Problem

You get a list of n distinct integers, all in the range 0 to n inclusive. Exactly one number from that range is absent. Return it. This is widely known as LeetCode 268, Missing Number.

Examples

nums = [4, 0, 1, 3]   ->  2     (n = 4, range 0..4)
nums = [0, 1]         ->  2     (the missing value can be n itself)
nums = [1]            ->  0

Approach 1: brute force

Put the values in a set and check each candidate from 0 to n.

def missing_number_set(nums):
    present = set(nums)
    for v in range(len(nums) + 1):
        if v not in present:
            return v

Complexity: O(n) time on average, O(n) space. (Sorting and scanning for the first gap is O(n log n) time.)

Approach 2: optimal (sum formula)

Key insight: you know exactly what the full range adds up to, so the shortfall is the missing number.

Walkthrough on [4, 0, 1, 3]: n = 4, expected sum 4 × 5 / 2 = 10, actual sum 8, missing 10 − 8 = 2.

def missing_number(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

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

Approach 3: XOR

XOR every index 0..n-1, the value n, and every element. Each present value meets its equal once and cancels; the missing value has no partner.

def missing_number_xor(nums):
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

On [4, 0, 1, 3]: 4 ^ (0^4) ^ (1^0) ^ (2^1) ^ (3^3) regroups as (4^4) ^ (0^0) ^ (1^1) ^ (3^3) ^ 2 = 2. Complexity: O(n) time, O(1) space, and no large intermediate values.

Tests

import random

for f in (missing_number, missing_number_xor, missing_number_set):
    assert f([4, 0, 1, 3]) == 2
    assert f([0, 1]) == 2                         # missing value is n
    assert f([1]) == 0                            # missing value is 0
    assert f([0]) == 1                            # single element
    assert f([]) == 0                             # empty: range is just 0

big = list(range(1_000_001))
big.remove(765_432)
random.seed(51)
random.shuffle(big)
assert missing_number(big) == missing_number_xor(big) == 765_432   # large n

for _ in range(300):
    n = random.randint(0, 20)
    full = list(range(n + 1))
    gone = full.pop(random.randrange(n + 1))
    random.shuffle(full)
    assert missing_number(full) == missing_number_xor(full) == missing_number_set(full) == gone

Edge cases and pitfalls

• The missing number can be 0 or n; a loop that only checks 0..n-1 misses the second case.
• In Java or C++, n * (n + 1) / 2 can overflow a 32-bit int for large n. Use a 64-bit type, subtract as you go, or use XOR.
• Use integer division // in Python so the result stays an int.

Where this shows up in data engineering

Gap detection in sequence numbers is routine: checking that a batch of message offsets, invoice numbers or daily partitions has no hole. Comparing the expected count or sum with the actual one is the cheap first check; a generate_series (or calendar table) anti-join then tells you exactly which values are missing when there may be more than one.