Tags: , , | Posted by Admin on 7/25/2009 10:43 PM | Comments (0)

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 Formula

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.

  1. void solution(vector<int> A)
  2. {
  3. int N=A.size(),i,j;
  4. vector<int> L(N,0);
  5. vector<int> R(N,0);
  6. vector<int> B(N,0);
  7. for (i=0,j=N-1; i=0 ;i++, j–)
  8. {
  9. L[i] = i==0? 1 : A[i-1] * L[i-1];
  10. R[j] = j==N-1? 1 : R[j+1] * A[j+1];
  11. }

  12. for (i=0; i
  13. {
  14. B[i] = L[i] * R[i];
  15. printf(“%d “,B[i]);
  16. }
  17. }


Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of i-th term. then finally we multiply it to get the result.

Comments are closed