Product Array

There is an array A[N] of N numbers. A Product Array P[N] of an array A[N] is defined such that for all i<N, P[i] = (product of all elements of A except A[i]).

 
For example, P[0] will be multiplication of A[1] to A[N-1] and P[1] will be multiplication of A[0] and from A[2] to A[N-1].

 
Solve this without using division operator and in O(N) time.

Solution :

1. Calculate backward product in product array P[i] = Product(A[i+1]*...*A[N])
2. Take a variable p=1
3. For each element of input, multiply it by p and multiply P[i] by p

Complexities :

• Time : O(N)
• Space : O(1)

Code :

void product_array(int[] input, int[] product, int N){

product[N-1] = 1;

for(int i=N-1; i>-1; i++){

product[i] = product[i+1]*input[i+1];

}

int p = 1;
for(int i=0; i<N; i++){

if(i > 0){

p *= input[i-1];

}

product[i] *= p;

}

}