Missing Number

This problem has four correct answers of increasing quality, and the interviewer wants to hear you move through them. The last two — a sum formula and an XOR — are both O(n) time and O(1) space, and the discussion of why you might prefer XOR is often the real test.

The problem

You get a list of n distinct integers, all taken from the range 0 to n inclusive. That range has n + 1 values, so exactly one is missing. Return it.

Example 1. [3, 0, 1] → 2. n = 3, the range is 0, 1, 2, 3, and 2 is absent.

Example 2. [0, 1] → 2. n = 2, and the missing value is the top of the range, n itself.

Example 3. [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8.

Constraints. 1 ≤ n ≤ 10⁴. All values are distinct and between 0 and n.

Clarifying questions

• Exactly one value missing, and no duplicates? Yes.
• Can n itself be the missing one? Yes — Example 2. Many first attempts forget this.
• Is the list sorted? No.
• May I modify the list? Assume not; it might be shared.

Approach 1: the simple way

Put the values in a set, then check 0, 1, 2 … n in order.

1def missing_number_set(nums: list[int]) -> int:2    """Brute force: remember what is present, then look for the gap."""3    present = set(nums)4    for value in range(len(nums) + 1):5        if value not in present:6            return value7    raise ValueError("nothing missing")

O(n) time and O(n) space. Sorting and checking sorted_nums[i] != i avoids the set but costs O(n log n). Both are fine at n = 10⁴, but the follow-up is always "can you do it in O(1) extra space?", so the real question is how to find the gap without remembering what you have seen.

The key insight

We know exactly what the full range should contain. So we do not need to remember the list — we only need to compare a summary of the list against the same summary of the full range. The difference is the missing value.

The first summary that comes to mind is the total. The range 0 to n adds up to n(n + 1) / 2. Subtract the list's sum and you have the missing number.

The second summary is XOR. Put every index 0 … n−1, plus n, together with every value. Each value that is present appears twice — once as an index-range member, once as a list value — and cancels. The missing value appears only once, in the range, and survives. That is Single Number again, with the "pairs" built from the range and the list.

Approach 2: the sum formula

1def missing_number_sum(nums: list[int]) -> int:2    """Expected total of 0..n minus the actual total."""3    n = len(nums)4    return n * (n + 1) // 2 - sum(nums)

On [3, 0, 1]: n = 3, the expected total is 3 × 4 / 2 = 6, the actual total is 4, and 6 − 4 = 2.

O(n) time, O(1) space. In Python this is perfect. In Java or C++ it has a trap: the expected total grows with n². At n = 10⁴ it is 50,005,000, comfortably inside a 32-bit int. But at n = 10⁵ it is 5,000,050,000, past the 32-bit limit of 2,147,483,647 — and the product n * (n + 1), which is computed before the division, already overflows at n = 46,341. Use a 64-bit type, or start a running total at n and add i - nums[i] at each index, so it never grows large.

Approach 3: XOR indices against values

1def missing_number(nums: list[int]) -> int:2    """XOR every index 0..n with every value; the missing one is left."""3    result = len(nums)              # n has no index of its own, so start with it4    for i, num in enumerate(nums):5        result ^= i ^ num           # cancel index against value6    return result

Step by step:

1. Seed result with n. The indices run 0 to n − 1, so n needs to be added by hand.
2. For each position, XOR in both the index and the value.
3. Every value that is present meets its equal among the indices (or the seed) and cancels. The missing value never meets a partner.

Dry run on [3, 0, 1]:

The final value is 2. In total the loop XOR-ed 3, 0, 1, 2 from the range and 3, 0, 1 from the list: 3, 0 and 1 each appear twice and cancel.

Complexity. O(n) time, one pass. O(1) space. XOR never makes a number wider than its inputs, so there is no overflow in any language.

Which to present? Both. Lead with the sum because it is easy to explain, raise the overflow risk yourself, and offer XOR as the version that cannot overflow.

Edge cases

• The missing value is n. [0, 1] → 2. The seed result = len(nums) handles it; code that only XORs indices 0 to n − 1 returns 0 here.
• The missing value is 0. [1] → 0. XOR gives 1 ^ 0 ^ 1 = 0.
• One element. [0] → 1 and [1] → 0. Both follow from the formula with no special case.
• Large n in a fixed-width language. Written as n * (n + 1) / 2 with 32-bit ints, the product passes the limit at n = 46,341, before the division even happens. XOR has no such limit.

Follow-ups

• "Two numbers are missing from 1 to n." XOR the range and the list to get a ^ b, then split by a differing bit exactly as in Single Number with two loners. Alternatively use both the sum and the sum of squares to set up two equations.
• "One number is duplicated and one is missing" (the set mismatch problem). XOR the range and the list: the result is duplicate ^ missing. Split by a set bit, then check which of the two candidates is in the list.
• "The list can be modified; find the smallest missing positive." That is a different problem: place each value at its own index (cyclic sort) and scan for the first mismatch, O(n) time and O(1) space.