Given an array *A[1...N]* of integers, create an array *O[1...N]* where *O[i]* = the product of all elements in A except for the ith element.

For example, if *N* = 3, and *A* = {6, 4, 2}, *O* = {8, 12, 24}

The tricky part: don't use divide and do it in *O(N)*.

The solution might be well known, but I thought it was interesting.

See Solution

The best solution I could come up with was to develop *O* in two passes, one forward, one backward:

1) Take a pass through *A* and store the "product so far" into *O*. So, the *i*th element of *O*, then, has the product *A[1]xA[2]x...xA[i-1]*.

2) Take a backwards pass through A and multiply the values in O by the "product so far" from the right. So, the ith element of O gets multiplied by the elements that come after it.

In both passes, the "product so far" is a single variable accumulating the product of the elements seen thus far in A.

The result is that *O[i]* will be the product of all the numbers before it and all the numbers after it.

## Comments

Sign uporlog in with Facebookto comment.yuktijainInstead of using 2 loops.. we can just add a check condition in the first loop.. if the loop variable id equal to i then no multiplication will be done.. for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(j!=i) k= k * a[j]; } o[i]= k; k=1;

Chris van EgmondI like the solution, indeed interesting, I hadn't seen this one yet.

yuktijain: the solution you give is an O(N^2) solution which is the trivial solution that this puzzle wants us to improve.

Karthik NaiduAlgorithm-> 1)find the product of all elements in the array .-O(n). 2)Run a loop through all elements and divide the product with that number and store in another array. -------------->Complexity = O(n+n)=O(2n)=>O(n). int i,j,prod=1; for(i=0;i<N;i++) { prod*=A[i]; //O(n) } for(i=0;i<N;i++) { O[i]=prod/A[i]; //O(n) }