Missing Number – Solution & Complexity
Solution Walkthrough
1. Use the range guarantee
- The numbers must be exactly the values from
0ton, except one missing entry. - That guarantee gives a closed-form expectation we can compare against the actual array.
2. Brute-force membership checks
- For every value from
0throughn, scan the array to see whether it exists. - This works, but the nested search costs
O(n^2)time.
3. Compare expected and actual totals
- The full range
0..nsums ton * (n + 1) / 2. - Since exactly one value is missing and nothing is duplicated, subtracting the actual array sum reveals that missing value immediately.
4. Compute the missing value in one pass
- First compute the expected range sum.
- Then subtract every number in the array and return the remainder.
5. Dry run / arithmetic trace
Trace nums = [3, 0, 1].
| quantity | value |
|---|---|
n | 3 |
expected sum 0 + 1 + 2 + 3 | 6 |
actual array sum 3 + 0 + 1 | 4 |
missing number expected - actual | 2 |
Because the array contains distinct numbers, no extra bookkeeping is needed beyond the running total.
6. Final solution and complexity
The sum formula finds the missing value in O(n) time and O(1) extra space.
