Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Let R be the repeated and M the missing value. Sum(a) − n(n+1)/2 = R − M.
  2. 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