Explorer
Data Structures & Algorithms

Find the one repeating and one missing number from 1 to n.

Problem Statement

You are given a read-only array of `n` integers from `1` to `n`. Each integer appears exactly once except `A` which appears twice and `B` which is missing. Return `[A, B]` where `A` is the repeating number and `B` is the missing number.

Examples

Input: arr = [3, 1, 2, 5, 3]

Output: [3, 4]

Explanation: 3 appears twice, and 4 is missing.

Input: arr = [3, 1, 2, 5, 4, 6, 7, 5]

Output: [5, 8]

Explanation: Combining the input according to Find the repeating and missing number logic yields [5, 8].

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

💡 Hint 1: Use math formulas for sum of first N natural numbers and sum of squares. 💡 Hint 2: S - Sn gives (repeating - missing), and S2 - S2n gives (repeating² - missing²). 💡 Hint 3: Solve the two linear equations to find repeating and missing in O(N) time and O(1) space.

Editorial & Approach

Problem Overview & Intuition

Using mathematical summation: Let X = repeating, Y = missing. Then sum(arr) - sum(1...N) = X - Y, and sum(arr²) - sum(1²...N²) = X² - Y² = (X - Y)(X + Y). Dividing gives X + Y, solving for both in O(1) auxiliary space.

Step-by-Step Approach

  1. Calculate expected sums sN = n*(n+1)/2 and s2N = n*(n+1)*(2n+1)/6.
  2. Compute actual sums s and s2 over arr.
  3. Derive diff = X - Y = s - sN.
  4. Derive sumXY = X + Y = (s2 - s2N) / diff.
  5. Solve: X = (diff + sumXY) / 2 and Y = X - diff.
  6. Return [X, Y].

Optimal Implementation (JavaScript)

function findRepeatingAndMissing(arr) {
  const n = arr.length;
  const sN = (n * (n + 1)) / 2;
  const s2N = (n * (n + 1) * (2 * n + 1)) / 6;
  let s = 0, s2 = 0;
  for (let num of arr) {
    s += num;
    s2 += num * num;
  }
  const val1 = s - sN;
  const val2 = (s2 - s2N) / val1;
  const repeating = (val1 + val2) / 2;
  const missing = repeating - val1;
  return [repeating, missing];
}

Complexity Analysis

Time Complexity O(N) — single pass to compute sum and sum of squares.
Space Complexity O(1) — constant extra space.

Edge Cases & Corner Traps Handled

  • Repeating is 1, missing is N.
  • Repeating is N, missing is 1.
  • Array of size 2.

Find the repeating and missing number

Hard
You are given a read-only array of `n` integers from `1` to `n`. Each integer appears exactly once except `A` which appears twice and `B` which is missing. Return `[A, B]` where `A` is the repeating number and `B` is the missing number.
Example Scenarios
1Example 1
Input: arr = [3, 1, 2, 5, 3]
Output: [3, 4]
Explanation:

3 appears twice, and 4 is missing.

2Example 2
Input: arr = [3, 1, 2, 5, 4, 6, 7, 5]
Output: [5, 8]
Explanation:

Combining the input according to Find the repeating and missing number logic yields [5, 8].

Editor
Loading Editor...
arr =
[3, 1, 2, 5, 3]
Output:Click "Run" above to execute and verify your code here.
[3,4]