Solution1

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

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


Solution:At each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting A[i]=a*b,where a=cumulative product of all those elements to the left of A[i] and b=cumulative product of all those elements to the right of A[i].

We can put this simply by storing the result in a separate array and by traversing the input array twice.

In the first iteration, we traverse the input array left to right and assign Output[i]=a (where a is the product of all the numbers preceding A[i]).

Now we traverse the input array again ,but in reverse direction and this time we find
b(here b is the product of all the numbers following A[i]) and Assign

Output[i]=Output[i]*b; which amounts to putting Output[i]=a*b

Hence Each Output[i] contains the product of all the elements in A except A[i].

Below is a C function to do the same.

int* function(int  input[],int size,int output[])
{
 long int result=1;
 for(int i=0;i<size;i++)
 {
  output[i]=result;
  result*=input[i];
 }
 result=1;
 for(int i=size-1;i>=0;i--)
 {
 output[i]*=result;
 result*=input[i];
 }
 return output;
}