2

Possible Duplicate:
Find two missing numbers

I been thinking for a while and can't seem to get an answer to this... So an array with n-2 unique integers in the range from 1 to n and O(1) space in addition to the space used by the array is given. How can you find the two integers from 1 to n that is missing in the array in O(n) time?

So for example, a = [4,3,1,6] and O(1) extra space How can you find 2, 5 in O(n) time?

Community
  • 1
  • 1
user1610574
  • 41
  • 1
  • 3
  • 2
    It's been answered many times before: http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe http://stackoverflow.com/questions/10218791/find-two-missing-numbers http://stackoverflow.com/questions/555744/algorithm-to-find-two-repeated-numbers-in-an-array-without-sorting – K Z Oct 05 '12 at 04:27

1 Answers1

3

Here's an idea: Just keep some statistic that gives you information about the missing numbers. For example, if you calculate the sum of all your numbers as S, then:

(1+2+..+N) - S = a+b

where a and b are your missing numbers. In your example, you get:

1+2+3+4+5+6 - 4+3+1+6 = 7 = a+b

You could then also do the same, for example, for multiplication and get:

(1*2*..*N) / S = a*b

in your case:

(1*2*3*4*5*6) / 72 = 10 = a*b

so the answer is 2 and 5.

Basically there are a lot of statistics you can use in this way...

Bitwise
  • 7,577
  • 6
  • 33
  • 50
  • the idea is interesting, but how do you know which numbers are missing, let say a + b = 7. (a, b) could be (1, 6) or (3, 4)? – Krypton Oct 05 '12 at 05:10
  • 1
    @Krypton because you also have the product which gives you a second constraint, so a*b=10, and since 1*6=6 and 3*4=12 the answer must be 2*5... – Bitwise Oct 05 '12 at 05:21
  • 1*2*3*....*n is NOT `O(1)` space, nor `O(N)` time. The assumption of integers ops being `O(1)` space and time is failing for repeating multiplications, since: `1 * 2 * ... * N = N!` To represent `N!` you are going to need `O(N*log(N))` bits. So, even if neglecting the `O(log(N))` bits for an integers (which is usually an assumption made), you cannot ignore the `N` factor – amit Oct 05 '12 at 07:10