Missing Number
Given an array holding n distinct numbers drawn from the range 0..n, find the one value from that range that is absent.
Open on LeetCode ↗Intuition
The answer everyone writes is n*(n+1)//2 - sum(nums), and in Python it passes. In C++ or Java with a large n it silently overflows: the triangular number grows quadratically, so it blows past a 32-bit int long before n itself does, and you get a wrapped-around garbage subtraction. The fix is not a bigger integer type — it is picking an operation that cannot overflow in the first place. XOR never grows a number; it only rearranges bits, so the result always fits in the same width as its inputs. Now use the property that makes XOR useful: a ^ a = 0 and a ^ 0 = a. Fold every index 0..n and every value in the array into one running accumulator, and each number that is genuinely present appears twice — once as an index, once as a value — and annihilates itself. The missing number appears exactly once, as an index with no matching value, so it is the only thing left standing. That is the invariant: at every step, the accumulator holds the XOR of exactly those numbers seen an odd number of times.
XOR every index together with every value, and each present number cancels against its own index. What survives is the one index with no matching value — the missing number. Folding in n at the end covers the index the loop can't reach.
Approach
Reject the sum formula for the right reason
The Gauss sum is elegant and O(n), so it is not wrong on complexity — it is wrong on arithmetic safety. For n near 100,000 the triangular number already exceeds 5 billion, past the 32-bit signed ceiling, and in a fixed-width language the value wraps. The result may even come out right by accident when both sides wrap identically, which makes it a bug that hides in testing. Reaching for an overflow-immune operation is the durable habit.
Pair each index with each value using XOR
The array has n slots but the range 0..n holds n+1 candidates. Walk the array once and fold in both the loop index i and the element nums[i]. Every value that is actually present will get XOR-ed in twice — once when its index comes up, once when it appears as an element — and those two copies cancel to zero. XOR is commutative and associative, so the order of the folding is irrelevant; the pairs find each other no matter how the array is shuffled.
Fold in n by hand, because the loop never reaches it
The loop index only runs 0 to n-1, so the candidate n itself is never offered. XOR it in explicitly, either before or after the loop, and now every one of the n+1 candidates has been contributed exactly once as an index. Combined with the n values from the array, that gives every present number exactly two appearances and the missing number exactly one. Whatever survives is the answer.
Solution & live demo
Common pitfalls
Forgetting the final index
for i, v in enumerate(nums):
x ^= i ^ v
return xx ^= len(nums) return x
The array has n entries but the range is 0..n, so index n never appears in the enumeration. Without folding it in, the answer is wrong whenever the missing number isn't n itself.
Using the sum formula without widening
return n * (n + 1) // 2 - sum(nums)
x ^= i ^ v
The Gauss sum is elegant and correct in Python, but n * (n + 1) / 2 overflows a 32-bit int for large n in C++/Java. XOR has no magnitude at all, so it can't overflow.
Sorting to find the gap
nums.sort()
for i, v in enumerate(nums):
if i != v: return ifor i, v in enumerate(nums):
x ^= i ^ vO(n log n) and it mutates the input, when the cancellation property gives the answer in one linear pass with no extra space.
Edge cases
0 XOR-ed in as an index has no matching value to cancel it — but XOR-ing 0 changes nothing, so the pairs cancel to 0 and 0 is correctly returned.
The manual fold of n is what supplies it; without that line this case returns 0 instead.
Fold index 0, value 0, and n = 1: the zeros cancel and 1 survives, which is correct.
XOR operates bitwise and never produces a value wider than its inputs, so the range of n is irrelevant.