1

Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)

**No, it is a duplicate !!! some numbers in the given array may be duplicated. Please refer to the example at the bottom of my post. thanks !!! **

Given an array of size n, containing numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.

e.g. A = [2, 4, 5, 4, 6, 5], missing numbers are 3 and 1.

My solutions:

sort A with O(n lg n) then scan.

Or, scan and set up a new bool array B to mark whether a number in the given array appears or not, e.g. B[A[i]] = true or false. Then, scan the bool array to the false element whose index is the missing element. Time O(n) but space O(n).

Are there solutions of O(n) in time and O(1) in space ?

Attention: the method of sum and multiplication does not work.

For example, given A [2, 3, 2, 3], the missing numbers are : 1 and 4.

Suppose missing numbers are x and y.

we cannot get:

x + y = sum of 1 to n - sum of A

x * y = product of 1 to n / product of A

1 + 4 != 10 - 10

1 * 4 != 24/36

thanks

Community
  • 1
  • 1
user1002288
  • 4,860
  • 10
  • 50
  • 78

2 Answers2

2

If the data is unsorted, there is no way to assure you can find the missing values without looking at each one. So, worst case would be O(n) to find them. To determine which are missing, you could do it in O(1) by computing the factorial of n and sum(1..n) and dividing out of the product and subtracting from the sum each term you encounter. At the end you'd know which are missing by solving for a + b = remaining sum and a * b = remaining product. This is a cheat though since you are essentially doing a preliminary O(n) computation or else a table-lookup which has a space impact.

codekaizen
  • 26,990
  • 7
  • 84
  • 140
  • _"you could do it in O(1) by computing the factorial of n"_ - and how do compute that in O(1)? – Eric Feb 27 '15 at 23:34
0

codekaizen's idea can be adapted to make it workable:

Compute U = the sum of all the elements, and V = the sum of squares of all the elements.
If a and b are the missing elements, we have

a + b = n(n+1)/2 - U = W, say
a^2 + b^2 = n(n+1)(2n+1)/6 - V = X, say

Substitute b = W - a in the second equation to get

a^2 + (W - a)^2 = X

This is a quadratic equation in a, which you can solve.

TonyK
  • 16,761
  • 4
  • 37
  • 72
  • Attention: it is different from some classical questions. here, duplicated numbers are allowed. the method of sum and multiplication does not work. For example, given A [2, 3, 2, 3], the missing numbers are : 1 and 4. Suppose missing numbers are x and y. we cannot get: x + y = sum of 1 to n - sum of A , x * y = product of 1 to n / product of A , 1 + 4 != 10 - 10 , 1 * 4 != 24/36 – user1002288 Dec 24 '11 at 17:20