COME ON CODE ON

A blog about programming and more programming.

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 A)
{
int N=A.size(),i,j;
vector L(N,0);
vector R(N,0);
vector B(N,0);
for (i=0,j=N-1; i=0 ;i++, j–)
{
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

Written by fR0DDY

March 5, 2009 at 3:35 PM

Posted in Programming

Tagged with , , , , ,

3 Responses

1. 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

Neeraj

March 6, 2009 at 2:13 PM

2. 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:

```void ArrayMul(int buf[],int res[],size_t len) /*res[] is assumed to be of size len & all members initialized to 1 */
{
size_t i;
int left = 1,
right = 1;

for(i = 0; i<len;i++)
{
res[i] *= left;
res[lenn-i-1] *= right;

left *= buf[i];
right *= buf[len-i-1];
}
}```

nthrgeek

November 29, 2009 at 9:49 PM

• nice solution and yes you are right.

fR0D

November 29, 2009 at 9:59 PM