Monday, March 19, 2012

Product of elements in an Array.


Given a list A with n elements, produce a list B with n elements such that the ith element of B is equal to the product of all elements except the ith in list A. Example: Given list A = [2, 3, 5, 8], make a function f(x) such that f(A) = [120, 80, 48, 30].


Approach:
1. for any i, in array A, calculate the left hand side product say L and right hand side product say R.
2. then for each i, multiply Li*Ri.


Trace:
left hand side product for each i in array A:
B = {1, 2, 6, 30}


int prod = 1;
for (int i=0; i<len; i++) {
B[i] = prod;
prod = prod * A[i];
}


Now calculate the right hand side product and multiply it with corresponding element in array B.
prod=1;
for (int i=len-1; i>=0; i--) {
B[i] = B[i]*prod;
prod = prod*A[i];
}


code input/output:
input array: 
2 3 5 8 
output array:
120 80 48 30

No comments:

Post a Comment