Missing Number

PracticeNeetCode ↗LeetCode ↗

Given an array nums containing n distinct numbers taken from the range [0, n], return the one number in that range that's missing from the array.

Example

Key Pointers

• The same XOR-cancellation trick from Single Number applies: XOR every index 0..n with every value in nums, and everything but the missing number pairs off and cancels.
• Because nums has n elements but the range is [0, n] (n + 1 numbers), there's always exactly one index with no matching value.
• A sum-based approach (n*(n+1)/2 - sum(nums)) also works, but XOR avoids any risk of integer overflow in other languages.

Step-by-Step Analysis

1. Initialize result = len(nums) (this accounts for index n, which has no corresponding array slot).
2. For each index i and value n in nums: update result ^= i ^ n.
3. Every index/value pair that exists cancels out through XOR, leaving only the unmatched number.
4. Return result.

Complexity

Time: O(n) — Space: O(1)

Code

def missingNumber(nums: list[int]) -> int:
    result = len(nums)
    for i, n in enumerate(nums):
        result ^= i ^ n
    return result

Code Explanation

How the solution above works, piece by piece.

1. XOR together every index 0..n−1, the number n itself, and every value in the array.
2. Each number that is present appears twice (once as an index or n, once as a value) and cancels to 0.
3. The missing number appears only once, as an index, so it's what remains.
4. result starts at len(nums) because that index doesn't exist in the loop.
5. O(n) time, O(1) space, with no risk of overflow (unlike summing).

Visual Walkthrough

Running it on nums = [3, 0, 1]:

Video Explanation

NeetCode — Blind 75, LeetCode 268