Missing Number — Arithmetic Series Difference
Compute the expected sum of 0..n and subtract the observed sum to recover the missing value in constant space.
Problem Statement
Given n distinct numbers drawn from 0..n, return the single number in the range that is absent.
Why This Problem Matters
- Shows how leveraging constraints (contiguous ranges) leads to O(1) space solutions.
- Provides a gentle entry into reasoning with arithmetic progressions.
- Common interview warm-up that tests for off-by-one errors.
Thought Process
Consider auxiliary structures
A boolean array works but costs O(n) extra space, which the follow-up asks you to avoid.
Use arithmetic series
The sum of 0..n is n(n+1)/2; subtract the actual sum to reveal the missing number.
Check integer overflow
Inputs are small (n ≤ 10⁴), so 32-bit ints are safe, but it is good practise to reason about it.
Step-by-Step Reasoning
- Compute expected = n × (n + 1) / 2.
- Sum all elements of nums into actual.
- Return expected - actual.
- Optionally, verify edge cases like missing 0 or missing n.
Dry Run
nums = [3,0,1]
expected = 6, actual = 4, difference = 2 → missing number.
nums = [0,1]
expected = 3, actual = 1, difference = 2 → missing n itself.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
One pass to sum the numbers with constant extra storage.
Annotated Solution
public class MissingNumber {
public int missingNumber(int[] nums) {
int n = nums.length;
int expected = n * (n + 1) / 2;
int actual = 0;
for (int num : nums) {
actual += num;
}
return expected - actual;
}
}The numbers are guaranteed to cover 0..n with one hole. The arithmetic series formula instantly tells you what the total should have been, so the delta exposes the missing value.
Common Pitfalls
- Forgetting to include n in the expected sum formula leads to off-by-one errors.
- Casting to int after computing the sum in long prevents overflow but is unnecessary here; pick one approach and stick to it.
- Using XOR without considering order still works but is easier to mess up under pressure.
Follow-Up Questions
- How would you solve the follow-up where exactly two numbers are missing?
- Can you stream the numbers and still recover the missing element?