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?
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) = sum<sub>n</sub> + A - B
because A replaces B. If we re-arrange, we get that:
sum(A) - sum<sub>n</sub> = 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) - sum<sub>n</sub> = A - B 2*sum(A) - 2sum<sub>n</sub> = 2A - 2B
That system is linearly dependent so that obviously won’t work.
The second option results in:
sum(A)<sup>2</sup> - sum<sub>n</sub><sup>2</sup> = A<sup>2</sup> - B<sup>2</sup> = (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.
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]