Repeat and Missing Number Array

Time

O (n)

Space

O (1)

Problem

InterviewBitOpen original problem

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 and B.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Note that in your output A should precede B.

Example:

1
Input:[3 1 2 5 3]
2

3
Output:[3, 4]
4

5
A = 3, B = 4

Solution approach

Intuition

Let A be the repeated number and B the missing one. Comparing the array with the ideal list 1..n gives two equations:

Sum: $\sum (1..n) - \sum A_i = B - A$
Sum of squares: $\sum (1..n)^2 - \sum A_i^2 = B^2 - A^2 = (B - A)(B + A)$

Dividing the second difference by the first gives $B + A$ . With $B - A$ and $B + A$ known, both numbers follow, and no extra array or sorting is needed.

Algorithm

In one loop, accumulate sm (sum of elements), sm2 (sum of their squares) and sm4 (sum of $i^2$ for $i = 1..n$ ).
Compute sm1 = n(n + 1) / 2 and rel1 = sm1 - sm, which is $B - A$ .
Compute rel2 = (sm4 - sm2) / rel1, which is $B + A$ .
Swap so that rel1 holds the larger value $B + A$ and rel2 holds $B - A$ .
Then x = (rel1 + rel2) / 2 is the missing number $B$ and y = (rel1 - rel2) / 2 is the repeated number $A$ . Return {y, x}.

Complexity

Time: $O(n)$ — one pass over the array.
Space: $O(1)$ — a handful of counters.

Edge cases

Large values: A[i] * A[i] and (i + 1) * (i + 1) are computed in int before being added to the long long sums, so they overflow once values pass about $46340$ .

Code

1
vector<int> Solution::repeatedNumber(const vector<int> &A) {
2
    long long sm = 0, sm1 = 0, sm2 = 0, sm4 = 0;
3
    long long n = A.size();
4
    for (int i = 0; i < n; i++) {
5
        sm += A[i];
6
        sm2 += A[i] * A[i];
7
        sm4 += (i + 1) * (i + 1);
8
    }
9
    sm1 = (n * (n + 1ll) / 2ll);
10
    long long rel1 = sm1 - sm;
11
    long long rel2 = (sm4 - sm2) / rel1;
12
    if (rel1 < rel2) swap(rel1, rel2);
13
    long long x = (rel1 + rel2) / 2ll;
14
    long long y = (rel1 - rel2) / 2ll;
15
    vector<int> aa = {y, x};
16
    return aa;
17
}

Give it a try first

Attempt the problem on InterviewBit — the code will still be here.