Missing Number Solution

Problem

You're given an array of n distinct numbers that are drawn from the range [0, n] — so there are n + 1 possible values but only n slots, meaning exactly one value is absent. Find and return that missing value.

Input: nums = [3, 0, 1]
Output: 2
Explanation: The four values 0–3 are expected but only 0, 1, and 3 are present, so 2 is missing.

Counter-example (missing value at the boundary): nums = [1, 2, 3] → output 0. The missing element can be any value including the endpoints of the range.

Intuition

The problem reduces to: which integer between 0 and n is not represented? A hash set can answer membership queries in O(1), making a single scan sufficient. But even better, the full range has a known sum — the Gauss formula gives us the total of 0 through n in one multiplication. The gap between that expected sum and the actual sum is the missing number, using no extra memory.

Approach 1 — Hash Set

Load all numbers into a set for constant-time lookup, then scan from 0 to n until something is absent.

Build a hash set from all elements in nums.
Iterate number from 0 to n inclusive.
Return the first number not found in the set.

1def missingNumber(nums: list[int]) -> int:
2    num_set = set(nums)
3    for number in range(len(nums) + 1):  # range is [0, n], so len+1 values
4        if number not in num_set:
5            return number

Time: O(n) — one pass to build the set, one pass to scan for the gap.
Space: O(n) — the hash set holds all n input values.

Approach 2 — Gauss Sum

The sum of integers from 0 to n is always n * (n + 1) / 2. Subtract the actual array sum and the difference is the missing value.

Compute n = len(nums).
Calculate expected_sum = n * (n + 1) / 2 using the closed-form Gauss formula.
Sum all elements in nums to get actual_sum.
Return expected_sum - actual_sum — the single missing contributor.

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

Time: O(n) — a single pass to compute the actual sum.
Space: O(1) — only two integer accumulators regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Hash Set	O(n)	O(n)	When the Gauss trick isn't obvious and clarity matters more than memory
Gauss Sum	O(n)	O(1)	The standard choice — constant space with the same linear time

Common Mistakes

Including only range(n) instead of range(n + 1) — the range is [0, n] so there are n + 1 candidate values; stopping at n - 1 misses the case where n itself is the absent element.
Integer overflow in Java and C++ — n * (n + 1) can exceed int range for large n; always compute expectedSum using long before dividing by 2.
Assuming the missing value is never at the boundaries — the missing number can be 0 (e.g., [1, 2, 3]) or n (e.g., [0, 1, 2]); both endpoints are valid answers.
XOR approach: forgetting to seed with n — the XOR trick XORs all indices 0..n with all values; a common error is only XOR-ing indices 0..n-1, which misses pairing the value n and produces a wrong result.
Rebuilding the set for repeated queries — if called in a loop, rebuilding the set each time is O(n²) overall; for a one-off query the hash set is fine, but recognize the trade-off.

Missing Number — Solution