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