All the below questions are to be done in O(n) time complexity.
1>Given an array of size n1 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 readonly.
2>Given an array of size n2 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> A)
 {
 int N=A.size(),i,j;
 vector<int> L(N,0);
 vector<int> R(N,0);
 vector<int> B(N,0);
 for (i=0,j=N1; i=0 ;i++, j–)
 {
 L[i] = i==0? 1 : A[i1] * L[i1];
 R[j] = j==N1? 1 : R[j+1] * A[j+1];
 }

 for (i=0; i
 {
 B[i] = L[i] * R[i];
 printf(“%d “,B[i]);
 }
 }
Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of ith term. then finally we multiply it to get the result.