Tuesday, June 22, 2010

Simple but interesting problem :-)

I recently came across this interesting problem and i thought its worth posting it.

Given an array A as input, produce an output array B such that every element of B, B[i] is the product of all the elements of A, except A[i] (E.g.: Suppose A is of size 4, then B[0] will be A[1]*A[2]*A[3] and B[1] will be A[0]*A[2]*A[3] and so on).

Sounds like a basic question right. Obviously there are more constraints. Rather just two constraints, do it in O(n) time without using the division operation.

Any innovative solutions welcome :-)