Missing Number: Find the Gap with Gauss's Sum Formula
Solve Missing Number in O(n) time and O(1) space using the Gauss sum formula — expected sum minus actual sum. Walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You're handed an array holding n distinct numbers drawn from the range 0 to n. That range has n + 1 slots but the array only has n of them, so exactly one number never shows up. Find it.
The lazy answer is a hash set. The elegant answer is one line of arithmetic that needs zero extra memory — and it comes from a trick a ten-year-old Carl Friedrich Gauss reportedly used to sum 1 through 100 in seconds. That reframe is the whole lesson here.
The problem
Given an array nums containing n distinct integers taken from the range [0, n], return the single number in that range that is missing from the array.
Input: nums = [3, 0, 1]
Output: 2 // range is 0..3; the array has 3, 0, 1 — so 2 is missingTwo facts do all the heavy lifting:
- The array length is
n, but the numbers span0throughninclusive — that'sn + 1possible values, so precisely one is absent. - Every number is distinct, so there are no duplicates to confuse the counting.
The brute force baseline
The direct approach: for every candidate v in 0..n, scan the array to see whether it appears. The first candidate that's absent is the answer.
function missingNumber(nums) {
const n = nums.length;
for (let v = 0; v <= n; v++) {
if (!nums.includes(v)) return v;
}
return -1;
}This is correct but wasteful. nums.includes(v) is itself an O(n) scan, and you run it up to n + 1 times, so the whole thing is O(n²). On a 10⁵-element array that's ten billion comparisons for a problem that needs almost none.
A hash set fixes the time — dump every value into a Set, then loop 0..n and return the first missing one. That's O(n) time, but it spends O(n) extra space to store the set. We can do better on both fronts at once.
The key insight: expected sum minus actual sum
Stop searching. Start counting.
If no number were missing, the array would contain every value from 0 to n, and their total would be a fixed, known quantity. Gauss's formula gives it instantly:
expected = 0 + 1 + 2 + ... + n = n * (n + 1) / 2Now add up the numbers you actually have. Exactly one value is missing, so your real sum falls short by precisely that value. The gap between the two sums is the answer:
missing = expected - actualNo lookups, no set, no second pass over a range. One formula, one accumulation loop, one subtraction. This is the math / Gauss sum pattern: replace a search with an invariant that the missing element perturbs in a measurable way.
The optimal solution
This is exactly the algorithm the visualizer steps through: compute the expected total with Gauss's formula, sum the array in a single pass, and return the difference.
var missingNumber = function (nums) {
const n = nums.length;
const expected = (n * (n + 1)) / 2;
let actual = 0;
for (let i = 0; i < n; i += 1) {
actual += nums[i];
}
return expected - actual;
};expected is the total the array should have; actual is what it does have. Because only one number is gone and all others are present exactly once, expected - actual collapses to the missing value alone. Everything else cancels out.
One practical note: for very large n, n * (n + 1) / 2 can overflow fixed-width integers in languages like Java or C++. There the safe variant accumulates expected - actual together as you go, or uses XOR. In JavaScript, numbers are 64-bit floats, so the straight formula is fine for LeetCode's constraints.
Walkthrough
Trace nums = [3, 0, 1]. Here n = 3, so expected = 3 * 4 / 2 = 6.
| Step | i | nums[i] | actual (running sum) | Note |
|---|---|---|---|---|
| Formula | — | — | 0 | expected = 3 × 4 / 2 = 6 |
| 1 | 0 | 3 | 0 + 3 = 3 | add nums[0] |
| 2 | 1 | 0 | 3 + 0 = 3 | add nums[1] |
| 3 | 2 | 1 | 3 + 1 = 4 | add nums[2] |
| Return | — | — | 4 | expected − actual = 6 − 4 = 2 |
The loop touches each element once and never looks back. After the final add, actual = 4. The complete range 0..3 should sum to 6, so the array is short by 6 - 4 = 2 — and 2 is exactly the value never added. The gap is the missing number.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
Brute force (includes) | O(n²) | O(1) | an O(n) scan repeated for each of n+1 candidates |
| Hash set | O(n) | O(n) | one pass to build the set, one to probe it |
| Gauss sum | O(n) | O(1) | single pass to sum; the formula is constant work |
The Gauss version wins on both axes versus the hash set: same linear time, but the only variables it keeps are expected, actual, and the loop index — constant space regardless of array size.
Common mistakes
- Getting the range wrong. The numbers span
0..ninclusive (n + 1values), but the array length isn. Usingn - 1or forgetting the+ 1in the formula gives an off-by-one answer. - Integer overflow in typed languages. In Java/C++,
n * (n + 1) / 2can exceedintrange for largen. Subtract incrementally (sum += i - nums[i]) or use XOR instead. JavaScript's doubles sidestep this at LeetCode scale. - Assuming the array is sorted. It usually isn't —
[3, 0, 1]is a valid input. The sum approach doesn't care about order, which is exactly why it beats any scan-and-compare that expects sorted data. - Reaching for a Set out of habit. It works and it's O(n) time, but it burns O(n) space for a problem that a single subtraction solves in place.
Where this pattern shows up next
Summing or scanning an array in one pass — and reasoning about what a single element changes — is the backbone of a whole family of array problems:
- Remove Duplicates from Sorted Array — an in-place single pass that compacts an array with O(1) extra space, same space discipline.
- Remove Element — the two-index write pattern for filtering an array as you walk it.
- Reverse String — another O(1)-space in-place transformation over an array.
- Best Time to Buy and Sell Stock — a single left-to-right pass that tracks a running quantity, just like this running sum.
You can also step through Missing Number interactively to watch the expected and actual sums race each other and the gap resolve to the answer.
FAQ
Why does the Gauss sum formula find the missing number?
The complete range 0 through n has a known total: n * (n + 1) / 2. Because the array contains every value in that range except one, its actual sum is short by exactly the missing value. Subtracting the actual sum from the expected sum cancels every present number and leaves only the absent one, so expected - actual is the answer directly.
What is the time and space complexity of the Missing Number solution?
The Gauss sum approach runs in O(n) time and O(1) space. It makes a single pass to accumulate the array's sum, and the expected total is a constant-time formula. It stores only a few scalar variables, so unlike the hash-set method — which is also O(n) time but O(n) space — it uses no extra memory that grows with the input.
Can I solve Missing Number with XOR instead?
Yes. XOR every index 0..n together with every array value; identical numbers cancel to zero, leaving the one index that has no matching value — the missing number. XOR is O(n) time and O(1) space like the sum approach, and it avoids integer overflow entirely, which makes it the preferred variant in fixed-width-integer languages.
Does the array need to be sorted first?
No. The sum method adds all the elements regardless of order, so [3, 0, 1] and [0, 1, 3] produce the same total and the same answer. Sorting would cost O(n log n) and buy you nothing here — one of the reasons the arithmetic reframe is stronger than any approach that scans for a specific value.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.