Missing Number: XOR and Math Approaches
LeetCode Missing Number (Problem 268) asks: given an array nums containing n distinct numbers from the range [0, n], return the only number in the range that is missing from the array.
The array has n elements but the range has n + 1 values (0 through n). Exactly one value is absent. Your job is to find it in O(n) time and O(1) extra space.
The problem
You are given nums = [3, 0, 1]. The length is 3, so the range is [0, 1, 2, 3]. The array contains 0, 1, and 3 but not 2. The answer is 2.
The approach
There are two clean ways to solve this. Both run in linear time with constant space. They just use different math.
XOR approach
You already know from the Single Number problem that XOR cancels pairs. If you XOR all the indices 0 through n together with all the values in the array, every number that appears in both sets cancels to 0. The only number left is the one that appeared in the index set but not in the array. That is the missing number.
The trick is to initialize result to n (since the loop indices only go from 0 to n - 1), then XOR each index and each value into it. At the end, result holds the missing number.
Sum approach
This one uses the Gauss formula. The expected sum of all numbers from 0 to n is n * (n + 1) / 2. The actual sum of the array is whatever you get when you add up its elements. The difference between the two is the missing number.
The XOR approach avoids potential integer overflow issues that the sum approach can have in languages with fixed-width integers. In Python this does not matter since integers grow arbitrarily large. But in Java, C++, or similar languages, XOR is the safer choice because it never produces a value larger than n.
The solution
XOR approach:
def missing_number(nums):
result = len(nums)
for i, num in enumerate(nums):
result ^= i ^ num
return result
Sum approach:
def missing_number_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
Step-by-step walkthrough
Let's trace both approaches on nums = [3, 0, 1]. The expected answer is 2.
Sum approach: nums = [3, 0, 1], n = 3
Gauss formula gives the expected sum. Subtract the actual sum and you have the answer.
XOR approach: nums = [3, 0, 1], n = 3
Initialize result to n, then XOR each index and value. Pairs cancel and the missing number survives.
Both approaches arrive at 2. The XOR version works by cancelling matched index-value pairs. The sum version works by subtracting what you have from what you should have. Pick whichever feels more natural to you.
Complexity
| Approach | Time | Space |
|---|---|---|
| XOR | O(n) | O(1) |
| Gauss sum | O(n) | O(1) |
Both solutions make a single pass through the array. Neither allocates any extra data structures. They are equally optimal in terms of time and space.
Building blocks
This problem decomposes into two reusable building blocks that CodeBricks drills independently.
XOR accumulation (cancel paired values)
Initialize a result and XOR a set of values into it. Any value that appears an even number of times cancels to 0. Only unpaired values survive. Here you pair each array value with its corresponding index, so every number that is present cancels and the missing one remains.
result = n
for i, num in enumerate(nums):
result ^= i ^ num
This is the same pattern used in Single Number and many other bit manipulation problems. The key insight is that XOR is its own inverse: a ^ a = 0 and a ^ 0 = a.
Gauss sum (expected minus actual)
Compute the expected sum of a contiguous range using the closed-form formula, then subtract the actual sum. The difference is whatever is missing (or extra, depending on the problem).
expected = n * (n + 1) // 2
actual = sum(nums)
missing = expected - actual
This pattern shows up whenever you know the range a set of numbers should span. It is useful for detecting missing elements, duplicates, and corrupted values.
Edge cases
Missing 0. If nums = [1], the range is [0, 1]. The sum approach gives 1 * 2 / 2 - 1 = 0. The XOR approach gives 1 ^ 0 ^ 1 = 0. Both handle this correctly without any special logic.
Missing n. If nums = [0, 1], the range is [0, 1, 2]. The missing number is n = 2. The sum approach gives 2 * 3 / 2 - (0 + 1) = 2. The XOR approach starts with result = 2, then XORs 0 ^ 0 = 0 and 1 ^ 1 = 0, leaving 2.
Array of length 1. If nums = [0], the answer is 1. If nums = [1], the answer is 0. Both are single-element arrays with n = 1, and both approaches handle them in a single iteration.
From understanding to recall
This problem is a great example of how two different mental models (bit manipulation and arithmetic) lead to the same result. In an interview, you want to be able to reach for either approach instantly. The XOR version requires you to remember the initialization trick (start with n). The sum version requires you to remember the Gauss formula. Both are short enough to write from memory after a few repetitions.
The real skill is not memorizing the code. It is recognizing that "find the missing element in a contiguous range" maps directly to either XOR accumulation or expected-minus-actual subtraction. Once that pattern fires automatically, you can solve this problem in under a minute.
Related posts
- Single Number - The classic XOR cancellation problem. Every element appears twice except one. Same XOR accumulation pattern, different setup.
- First Missing Positive - A harder variant where the range is not given and you must use cyclic sort. Missing Number is the gentle introduction to this family.
- Contains Duplicate - Uses a hash set to detect duplicates. A different tool for a related class of "what is present or absent?" questions.