Practice › Arrays
Repeating and Missing Number
Medium · Arrays · Asked at Amazon, Samsung, Microsoft, TCS, Infosys
The array should contain each of 1..n exactly once, but one value R appears twice and one value M is missing. Print R M.
Input
First line: n. Second line: n space-separated integers.
Output
Two integers: the repeating number and the missing number.
Constraints
- 2 ≤ n ≤ 10^5
Compare the actual sum and sum of squares with the expected ones: S − S₀ = R − M and S₂ − S₂₀ = R² − M² give two equations.
Example 1
Input
5 3 1 2 5 3
Output
3 4
Example 2
Input
2 1 1
Output
1 2
Hints
- Let R be the repeated and M the missing value. Sum(a) − n(n+1)/2 = R − M.
- The sum of squares gives R² − M² = (R − M)(R + M), so you can get R + M too.
Approach
Compute d1 = S − n(n+1)/2 = R − M and d2 = S2 − n(n+1)(2n+1)/6 = R² − M². Then R + M = d2 / d1, so R = (d1 + d2/d1) / 2 and M = R − d1. With n ≤ 10^5 the sum of squares stays below 10^15, so 64-bit integers are enough. (A counting array or the XOR trick also works.)
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long s = 0, s2 = 0, x;
for (int i = 0; i < n; i++) {
cin >> x;
s += x;
s2 += x * x;
}
long long d1 = s - n * (n + 1) / 2;
long long d2 = s2 - n * (n + 1) * (2 * n + 1) / 6;
long long sum = d2 / d1;
long long R = (d1 + sum) / 2, M = R - d1;
cout << R << " " << M << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
d1 = sum(a) - n * (n + 1) // 2
d2 = sum(x * x for x in a) - n * (n + 1) * (2 * n + 1) // 6
total = d2 // d1
R = (d1 + total) // 2
print(R, R - d1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long s = 0, s2 = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
s += x;
s2 += x * x;
}
long d1 = s - n * (n + 1) / 2;
long d2 = s2 - n * (n + 1) * (2 * n + 1) / 6;
long sum = d2 / d1;
long R = (d1 + sum) / 2;
System.out.println(R + " " + (R - d1));
}
}Solve Repeating and Missing Number online · All practice problems