Find the repeating and the missing number

Medium

Problem

An array of size n should contain every number from 1 to n exactly once. Instead, one number appears twice and one is missing. Return both.

Example 1

Input:  [3, 1, 3]
Output: repeating = 3, missing = 2

Also asked as: Find the repeating and the missing

Test cases

Case 1

Input:    [3,1,3]
Expected: {"repeat":3,"missing":2}

Case 2

Input:    [1,2,2,4]
Expected: {"repeat":2,"missing":3}

Case 3

Input:    [2,2]
Expected: {"repeat":2,"missing":1}

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sum and sum-of-squares

Time O(n)Space O(1)

Let S = Σa − Σ1..n = repeat − missing, and P = Σa² − Σi² = repeat² − missing². Solve the two equations.

function repeatAndMissing(a) {
const n = a.length;
let s = 0, p = 0;
for (let i = 1; i <= n; i++) {
s += a[i - 1] - i;
p += a[i - 1] * a[i - 1] - i * i;
}
// s = r - m, p = r^2 - m^2 = (r - m)(r + m) => r + m = p / s
const sum = p / s;
const repeat = (s + sum) / 2;
return { repeat, missing: repeat - s };
}

XOR method avoids overflow: xor all a and 1..n, isolate a set bit, bucket into two groups.