Problem with question,
Python code it runs in 2*n so it is O(n)
length=7
num=[4,3,1,6,2]
num2=[0]*length
i=1
temp=1
while i<=length-2:
num2[num[i-1]-1]=1
i+=1
i=0
while i<length:
{if (num2[i]!=1):
{ print((i+1)," is missing")}
i+=1
}
The problem seem trivial but it is not you need to read it carefully as the requirement is O(1) space but your solution is O(N)
The idea is simple
Call
S1_100 = 1 + 2 +3 + ...100;
S2_100 = 1 ^ 2 + 2 ^ 2 + .. + 100 ^ 2;
Now we do the computation on the data that we have
S1_A = a[1] + a[2] + .. a[98]
S2_A = a[1]^2 + a[2]^2 + .. a[98]^2
Now let say the two missing number are a and b then
a + b = S1_100 - S1_A
a^2 + b^2 = S2_100 - S2_A
We then determine a and b from the equations.
Apply in your problem we have
S1_5 = 1 + 2 + 3 + 4 + 5 = 15
S2_5 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55
S1_A = 4 + 1 + 2 = 7
S2_A = 21
The
x + y = 8
x^2 + y ^ 2 = 34
The solution is x = 3, y = 5;
Yep,if i have understood you correctly your solution is based upon next formula
(x + y) ^ 2 = x^2 + 2*x*y + y^2
so 2*x*y = (x + y)^2 - x ^ 2 - y ^ = 30
so x * y = 15. But we've encountered factorization problem. Can you clarifty how you handle this moment?
I've seen the problem before where only 1 number was missing and the solution is trivial.
The solution using 2 equations makes sense to me but what if the interviewer asks "why does that (using 2 equations) work?". for 3 missing numbers we would need 3 equations.. how do we prove this will work in general?
Here is the solution :-
- Feurer August 07, 2013a = [15, 25, 78, 21, 44, 93, 75, 98, 6, 11, 34, 17, 47, 14, 19, 58, 59, 83, 80, 62, 48, 74, 22, 39, 56, 72, 12, 49, 45, 57, 4, 55, 73, 8, 5, 100, 37, 68, 89, 77, 51, 2, 13, 53, 10, 9, 60, 63, 1, 52, 76, 16, 23, 97, 31, 42, 64, 18, 82, 81, 85, 7, 92, 69, 87, 50, 38, 84, 36, 66, 99, 94, 46, 95, 20, 30, 79, 54, 3, 96, 71, 28, 67, 61, 86, 41, 88, 43, 40, 29, 33, 35, 26, 90, 32, 27, 24, 91] f100 = 99 * 100 f = 1 s = 199 for i in range(1, 99): s = s + i - a[i - 1] f = f * a[i - 1] f100 = f100 * i f = f100 / f # a + b = s # a * b = f b = (s + (s**2 - 4 * f)**.5) / 2 a = s - b print int(a), int(b)