Find the repeating and the missing number
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}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.