## Google Interview Questions

All the below questions are to be done in O(n) time complexity.

**1>**Given an array of size n-1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as read-only.

**2>**Given an array of size n-2 whose entries are integers in the range [1, n], find two integer that are missing.

**3>**There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i].

or

Example:

INPUT:[4, 3, 2, 1, 2]

OUTPUT:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

**Solution** :

**1>**Let the missing number be M. We know that the sum of first N natural numbers is N*(N+1)/2. Traverse through the array once and calculate the sum. This is the sum of First N natural numbers – M or S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S.

**2>**Similar approach to the first one. Traverse the array once and calculate its sum and multiplication. Let the sum be S and multiplication be M. Let the missing numbers be P and Q. From above we know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q from these two equations.

**3>** Lets first see the C++ solution.

void solution(vector

{

int N=A.size(),i,j;

vector

vector

vector

for (i=0,j=N-1; i

{

L[i] = i==0? 1 : A[i-1] * L[i-1];

R[j] = j==N-1? 1 : R[j+1] * A[j+1];

}

for (i=0; i

There may be better solutions for Qno. 1 and 2

for qno. 1

//solution

res=0;

for(i=0;i<n;i++){

res=res XOR i

if(i<n-1)

res=res XOR arr[i]

}

after end of this loop res is the missing number

for qno.2

//repeat the above process

res is then XOR of two missing numbers

Now the question is can you find two numbers if there xor is given and you know the range in which they lie??

if you can find then do let me know..

The xor method is most generic and works even the sum of nos. exceeds the storage limits. this would be more of concern in 2nd case where we have n!

This method uses the property that x (*) x=0 and XOR is associative

NeerajMarch 6, 2009 at 2:13 PM

For the third problem : my solution consists of only one loop + you have used lots of extra spaces which is not at all necessary.

Some home cooked codes in C:

nthrgeekNovember 29, 2009 at 9:49 PM

nice solution and yes you are right.

fR0DNovember 29, 2009 at 9:59 PM