Find Missing and Repeating Number
An array holds numbers 1..n but one number is missing and another appears twice. Find both in O(n) time, O(1) space.
- 2 <= n <= 10⁵
- Array holds values in the range 1..n
- Exactly one value is missing and exactly one appears twice
Intuition
The find missing and repeating number problem hands you an array that should contain 1..n but where one number is missing and another appears twice. Both must be found in O(n) time and O(1) space — the space bound is what rules out the obvious solutions of a frequency array or a hash set.
With two unknowns, you need two independent equations. The array gives you exactly that.
Compare the array's sum against the expected sum of 1..n. The repeated number is counted once too many and the missing one not at all, so the difference is:
- S − Sₙ = R − M
One equation, two unknowns. Now do the same with squares. The sum of squares differs by R² − M², and that factorises as (R − M)(R + M). Since you already know R − M, dividing gives:
- R + M = (S² − S²ₙ) / (R − M)
Two linear equations in R and M, solved by adding and halving. Two passes over the array, a handful of arithmetic, no extra memory.
One caution: the sum of squares of 1..n grows as n³, so for n near 10⁵ it overflows a 32-bit integer. Use 64-bit arithmetic — this is the usual reason a correct-looking implementation fails on large inputs.
Two unknowns need two equations. The sum gives you R − M and the sum of squares gives you R² − M², which factors into (R + M)(R − M) — divide and you have their sum. Two linear facts, two values recovered in one pass with no extra space. Reach for this whenever a problem hides a small fixed number of unknowns in aggregate statistics.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n) time and O(1) space.
Recognise that two unknowns need two equations
A single sum leaves R and M underdetermined — many pairs share the same difference. The second equation is what pins them down, and squares are the natural choice because their difference factorises usefully.
Take the difference of sums
Compute the array's sum S and the expected sum n(n+1)/2. Their difference is exactly R − M, since the repeated value is counted twice and the missing one zero times.
Take the difference of squares
Compute the sum of squares and subtract the expected n(n+1)(2n+1)/6. That difference is R² − M², which factorises to (R − M)(R + M) — the step that makes the second equation solvable.
Divide to get the sum
Dividing the squares difference by the sums difference yields R + M directly. The division is exact because R − M is non-zero — the two numbers are distinct by the problem's definition.
Solve the two linear equations
With R − M and R + M known, R = ((R−M) + (R+M)) / 2 and M = R − (R−M). Both divisions are exact, since the two expressions always share the same parity.
Guard against overflow
The sum of squares up to n is on the order of n³, which exceeds a 32-bit integer well before n reaches 10⁵. Use 64-bit types, or the XOR-based alternative that avoids large intermediates entirely at the cost of a bit-partitioning step.
Cost of the arithmetic approach
Two passes computing sums give O(n) time and genuinely O(1) space — the constraint that rules out counting arrays. Every other step is constant-time arithmetic.
Solution & live demo
Common pitfalls
Sorting or using a frequency array
count = [0] * (n + 1) for x in nums: count[x] += 1
diff = s - sn ssum = (sq - sqn) // diff
Both work, but the counting array costs O(n) extra space and sorting costs O(n log n) time — and the follow-up explicitly asks for O(1) space in one pass. The algebra needs only two running totals.
Overflow on the sum of squares
int sq = 0; // in C++/Java for (int x : nums) sq += x * x;
long long sq = 0; for (int x : nums) sq += (long long)x * x;
Python integers grow without bound, so the Python version is safe — but with n near 10^5 the sum of squares exceeds a 32-bit int and any literal translation silently wraps. The widening cast has to happen before the multiply, not after.
Mixing up which value is which
M = (diff + ssum) // 2
R = (diff + ssum) // 2 M = R - diff
diff is R − M and ssum is R + M, so their half-sum is R, the repeating value. Assigning it to the missing one swaps the pair and returns the answer backwards.
Edge cases
Pure algebra — positions don't matter.
Sum of squares reaches ~n³/3; use 64-bit. Python unaffected.