GeeksforGeeks Hard

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.

arraymathbit-manipulation

Open on GeeksforGeeks ↗

02

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.

03

Approach

1

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.

2

Factor the squares

R² − M² = (R − M)(R + M), so dividing the second difference by the first gives R + M directly.

3

Solve

R = ((R−M) + (R+M)) / 2 and M = R − (R − M). Two O(n) passes worth of arithmetic, constant extra space.

04

Solution & live demo

python

▶1def find_missing_repeating(nums):
▶2    n = len(nums)
▶3    s  = sum(nums)
▶4    sq = sum(x * x for x in nums)
▶5    sn  = n * (n + 1) // 2
▶6    sqn = n * (n + 1) * (2 * n + 1) // 6
▶7    diff = s - sn                # R - M
▶8    ssum = (sq - sqn) // diff    # R + M
▶9    R = (diff + ssum) // 2
▶10    M = R - diff
▶11    return R, M

05

Edge cases

Repeat and missing adjacent, e.g. [1,2,2,4]

Pure algebra — positions don't matter.

Overflow in fixed-width languages

Sum of squares reaches ~n³/3; use 64-bit. Python unaffected.

06

Complexity

Time

O(n)

Space

O(1)

Two aggregate passes and constant algebra.