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.
Intuition
Two unknowns need two equations. The sum of the array differs from the expected 1..n sum by (repeat − missing), and the sum of squares differs by (repeat² − missing²). Divide the two and you get repeat + missing — now it's two linear equations.
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
Set up the two equations
Let R = repeating, M = missing. S − S_n = R − M and S² − S²_n = R² − M², where S, S² are the actual sums and S_n, S²_n the expected ones.
Factor the squares
R² − M² = (R − M)(R + M), so dividing the second difference by the first gives R + M directly.
Solve
R = ((R−M) + (R+M)) / 2 and M = R − (R − M). Two O(n) passes worth of arithmetic, constant extra space.
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.