간단한 퀴즈입니다.

You are given n consequent numbers not necessarily ranging from 1 to n, e.g., 3, 4, 5, …, and (3+n-1). From those n numbers, two numbers each of which is neither the smallest nor the biggest were removed. And the remaining n-2 numbers were shuffled and stored in an array.

Now, you want to find those two missing numbers. For example, given 11, 3, 5, 4, 8, 7, and 9, you want to find that 6 and 10 are missing. But you have the storage which is less than O(n) and you have O(n) time. How do you do that?

update:
One interesting answer is to use a quadratic equation. Suppose the Sv and Lv denote the smallest and the largest value in the array, respectively. Then, you can compute Sv + (Sv + 1) + … + Lv and Sv * (Sv + 1) * … * Lv. And then, you scan the array and compute the sum and the product of values. Now, suppose that those two missing numbers are A and B. From two sums and two products, you get A+B and A*B. So, this problem boils down to solving a quadratic equation.

However, this approach takes the space larger than O(n), because 1 * 2 * … * n = n! = O(n^n) and storing O(n^n) value needs O(nlogn) space.

푸신분은 답글을.. 질문도 답글로요.