Missing Number

Problem

You are given an array nums of n distinct integers drawn from the range [0, n] (that range holds n + 1 values, so exactly one is absent). Return the single number in [0, n] that does not appear in nums.

Examples

• [3, 0, 1] → 2 — n = 3, the full range is 0..3; 2 is missing.
• [0, 1] → 2 — n = 2, the full range is 0..2; 2 is missing.
• [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8 — n = 9; every value 0..9 is present except 8.

Constraints

• n == len(nums), 0 <= nums[i] <= n, and all nums[i] are distinct.
• 1 <= n <= 10^4

Follow-up: O(n) time, O(1) extra space, and without any risk of integer overflow.

Think about it first

TL;DR

XOR every index with every value so pairs cancel and the missing number remains — O(n) time, O(1) space, overflow-proof.

Approach 1 — Brute force: a hash set

Record every value that’s present, then scan 0..n for the one that isn’t.

def missingNumber(nums: list[int]) -> int:
    seen = set(nums)
    for i in range(len(nums) + 1):
        if i not in seen:
            return i
    return -1        # unreachable given the constraints

Complexity: O(n) time, O(n) space for the set.

This is correct, but the follow-up bans the extra O(n) space. The next two approaches reach O(1).

Approach 2 — Gauss sum (arithmetic)

The numbers 0, 1, ..., n add up to a closed-form total n(n + 1) / 2. The missing value equals that expected total minus the actual sum of the array.

def missingNumber(nums: list[int]) -> int:
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Walkthrough on [3, 0, 1]: n = 3, expected = 3 * 4 // 2 = 6, sum(nums) = 4, so 6 - 4 = 2.

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

Caveat: in a fixed-width language, expected and sum(nums) can each overflow for large n even though their difference fits. Python’s big integers dodge this, but that fragility is exactly why the XOR version is often preferred.

Approach 3 — XOR of indices and values

XOR cancels equal operands (x ^ x = 0) and is order-independent. XOR together both the indices 0..n and all the values in nums: every present number appears exactly twice, once as an index and once as a value, and cancels itself. The missing number appears only as an index, so it is the only value left. Because XOR never grows its operands, there is no overflow.

def missingNumber(nums: list[int]) -> int:
    result = len(nums)        # seed with n; the loop covers indices 0..n-1
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

We seed result with n because enumerate only yields indices 0..n-1; seeding covers the final index n, completing the full index set 0..n.

Walkthrough on [3, 0, 1] (result starts at 3):

Returns 2. The value 3 (from index 0) and the seeded index 3 cancel; 0 and 1 each cancel their own index; index 2 never meets a value 2, so 2 survives.

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

Common pitfalls

• Range off by one: the search/loop must cover 0..n inclusive (n + 1 values), not 0..n-1.
• Forgetting the seed in XOR: without initializing result = n, the highest index is never folded in and the answer is wrong whenever the missing number isn’t n.
• Overflow in the sum version: fine in Python, but flag it in languages with fixed-width integers — that’s the whole reason to prefer XOR.
• Assuming the array is sorted: it isn’t; both the sum and XOR methods work regardless of order, since addition and XOR are commutative.

Pattern takeaway

When elements pair up and exactly one is unmatched, use XOR: fold everything together and matched pairs vanish (x ^ x = 0), leaving the odd one out. It beats the sum approach whenever overflow is a concern, because XOR never enlarges its operands.