AlgoViz
HomeArrays & Hashing

Find the repeating and missing number

Hard

Two equations, two unknowns

Problem

Given an integer array nums of size n containing values from [1, n] and each value appears exactly once in the array, except for A, which appears twice and B which is missing. Return the values A and B, as an array of size 2, where A appears in the 0-th index and B in the 1st index. Note: You are not allowed to modify the original array.

In simple words

Count each value 1..n: the one seen twice repeats, the one never seen is missing.

The idea

Compare the array's sum and sum of squares against the expected values for 1..n. That gives x - y and x² - y², and dividing the second by the first yields x + y — two linear equations that solve for the repeated and missing numbers directly.

The trick

  • S - Sn = x - y and S2 - S2n = x² - y² = (x-y)(x+y).
  • Use 64-bit types: the sum of squares overflows 32 bits quickly.
  • A marking pass or XOR partition solves it too, also in O(n) with O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
5
4
1
1
0
1
2
3
4

Step 1 of 2. Here's the example — nums = [3, 5, 4, 1, 1] Values: 3, 5, 4, 1, 1.

1/2
Optimal
timeO(n)spaceO(1)
1// A = repeating, B = missing2S  = sum(nums) - n(n+1)/2            // = A - B3S2 = sum(x*x)  - n(n+1)(2n+1)/6      // = A^2 - B^24sum = S2 / S                         // = A + B5A = (S + sum) / 2;  B = A - S6return [A, B]

Input

array
[3, 5, 4, 1, 1]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [3, 1, 2, 5, 3]
Output:
[3, 4]
Explanation:
3 repeats and 4 is missing.

Example 2

Input:
nums = [1, 2, 2, 4]
Output:
[2, 3]
Explanation:
2 repeats, 3 is missing.

Example 3

Input:
nums = [2, 2]
Output:
[2, 1]
Explanation:
2 repeats, 1 is missing.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • n - 2 elements in nums appear exactly once and are valued between [1, n].
  • 1 element in nums appears twice, and is valued between [1, n].

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.