Missing Number (LeetCode 268)

The problem

You get an array of n distinct numbers taken from the range 0 to n. Exactly one number in that range is missing. Return it, ideally in O(n) time and O(1) extra space.

Input:  [3, 0, 1]
Output: 2

n = 3, so the range is 0, 1, 2, 3. The array has 0, 1 and 3, so 2 is missing.

How to think about it

Start with brute force. For each number from 0 to n, check whether it is in the array: O(n²). A set brings that down to O(n) time but O(n) space. Sorting and scanning for the first gap is O(n log n).

The key insight: pair every value with an index, and XOR cancels the pairs. The full range is 0, 1, ..., n. The array indices give you 0, 1, ..., n - 1, and starting the result at n adds the last one. So XOR-ing n, every index, and every value is the same as XOR-ing the full range and the array together. Every number that is present appears twice (once from the range, once from the array) and cancels to 0. The missing number appears once and survives.

The sum trick, and why XOR is safer. You could also compute n·(n + 1)/2 - sum(nums). In Python that is fine, but in languages with fixed-width integers the sum can overflow. XOR never grows beyond the width of the inputs.

Which pattern is this? Bit manipulation, XOR cancellation, the same idea as Single Number. The tell is “numbers from a known range, one missing (or extra)“.

Approach

1. Start r = n (the length of the array), which covers the last value of the range.
2. For each index i and value x, do r ^= i ^ x.
3. Return r.

Solution

def missing_number(nums):
    r = len(nums)               # covers the value n, which has no index
    for i, x in enumerate(nums):
        r ^= i ^ x              # present numbers cancel in pairs
    return r
# missing_number([3,0,1]) -> 2

Dry run

On [3, 0, 1], starting with r = 3:

Overall, r = 3 ^ (0^3) ^ (1^0) ^ (2^1). The 0s, 1s and 3s pair up; the lone 2 survives. The answer is 2.

Complexity

• Time: O(n). One pass.
• Space: O(1). One integer.

Edge cases and pitfalls

• Missing n itself ([0, 1]) returns 2: the starting value r = n is never cancelled.
• Missing 0 ([1]) returns 0.
• Forgetting to start at n is the classic bug: then the range covers only 0 to n − 1 and the answer is wrong.
• Assumes distinct values. With duplicates, the cancellation argument breaks.

Related problems

• Single Number (LeetCode 136): the XOR cancellation this solution reuses.
• Find the Duplicate Number (LeetCode 287): the opposite question, one value repeated in a known range.
• Single Number III (LeetCode 260): XOR when two values are left over.