read

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?

Ideas

This seems pretty similar to another problem.

You are given an n+1 array with values 1...n. All of the values are in the array once, except A, which is in the array twice. Return A.

This problem requires the solution to have the same runtime and space complexity as the last one. The solution for the second problem is simple:

def extra_value(A):
    n = len(A)
    sum_n = n * (n+1) / 2
    return sum(A) - sum_n

Because all of the values from 1...n exist in A, subtracting that from A leaves us with the element that repeats. Going back to the original problem, it's clear that:

sum(A) = sumn + A - B

because A replaces B. If we re-arrange, we get that:

sum(A) - sumn = A - B

All right so far this seems OK. I have to admit I actually got stuck at this point for a long time. The answer solution seemed so simple after I noticed that there's 2 unknowns, so I can just try to create another equation involving A and B and then solve the corresponding linear system. All right, but how would I change them the equations?

Two options come to mind:
a) multiply equality by 2
b) square equality

The first option results in :

sum(A) - sumn = A - B
2*sum(A) - 2sumn = 2A - 2B

That system is linearly dependent so that obviously won't work.

The second option results in:

sum(A)2 - sumn2 = A2 - B2
= (A-B)(A+B)

That works! The calculation involved for squaring each of the individual elements of A and 1...N is something we can easily do. Then, we can use our solution for (A-B) and divide the equality associated with (A-B)(A+B) by (A-B)

The resulting linear system is easy to solve.

Code

def repeatedNumber(self, A):

    n = len(A)

    sum_actual = sum(x for x in A)
    sum_n = n * (n + 1) / 2

    a_minus_b = sum_actual - sum_n

    inter_a = n * (n + 1) * (2 * n + 1) / 6
    inter_b = sum(x**2 for x in A)

    multi = inter_b - inter_a
    a_plus_b = multi / a_minus_b

    a = (a_minus_b + a_plus_b) / 2
    b = a_plus_b - a
    return [a, b]
Blog Logo

Abrar Hussain

I'm a student studying computer science at the University of Toronto. Previously, I spent some time interning at Amazon. I'm currently interning at Uber as a Software Engineer Intern.


Published

Image

Abrar Hussain

Back to Overview