Complexity of Missing numbers

Computer Science Level 2

Suppose that out of the integers from 1 to $n$ , you are given $n - 2$ of them.

What is the order of complexity of finding these 2 missing numbers?

O(\sqrt{n})

O(e^n)

O(n^2)

O(n)

1 solution

Calvin Lin Staff
Jan 31, 2015

Let the 2 missing numbers be $x, y$ .

$O(n)$ . Find the sum of the $n-2$ number.
$O(n)$ . Find the sum of squares of the $n-2$ numbers.

$O(1)$ .. We know that the sum of the $n$ numbers is $\frac{ n(n+1) } { 2 }$ , and the sum of the $n$ squares is $\frac{ n (n+1)(2n+1) } { 6}$ .

$O(1)$ . We know $x + y$ and $x^2 + y^2$ by subtracting. We then solve the quadratic to find these 2 numbers.

Hence, we have an $O(n)$ algorithm to find the numbers.

Now, since we need to read all of the input, the minimum time is of the order $O(n)$ .

Thus, the answer is $O(n)$ .

Clearly you can't do better than $O(n)$ ; you need to read the whole input and it takes $O(n)$ time already.

Ivan Koswara - 6 years, 4 months ago

Right, that was my argument too. However, i'm not always too certain about the most effective algorithm, so I placed the disclaimer. Let me remove it now.

Calvin Lin Staff - 6 years, 4 months ago

Complexity of Missing numbers

1 solution

0 pending reports