Blog # 39 : Product Array

Devise an algorithm :
There is an array A[N] of N numbers. Find a Product Array P[N] of an array A[N] which 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;
}
}

Courtesy : Vibhaj