Welcome to MindCipher, a social repository of the world's greatest brain teasers, logic puzzles and mental challenges.

Products Algorithm

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 ith 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


yuktijain

Instead 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 Egmond

I 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 Naidu

Algorithm-> 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) }

Check out other puzzles:
Random  

Like this? You might also like:
Count The Bits
Open Water
Don't Mate in One
Submitted by
ace25
over 1 year ago
Likes
Difficulty 4.0 ?

Tags
interview algorithm programming


Back