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 :-)

-Vignesh

5 comments:

  1. i tried using log() and exp() functions. It worked fine. Regardin de complexity i think its of order n... u want me to embed de code???

    ReplyDelete
  2. Great ! Log() is one possible solution. But there is a simpler solution that involves simple multiplication. You can accomplish this by carefully traversing the array twice without division.

    ReplyDelete
  3. First loop will traverse in forward direction on an array {a,b,c,d} and will store {1,a, ab, abc} in B.
    The second loop will traverse the array from the end and will store {bcd,cd,c,1} in temp. Now the answer is Array B * Array temp (i.e product of respective elements)....

    ReplyDelete
  4. This is almost the close solution. Because you have achieved the time complexity of O(n) and without division. But you are using an additional space of O(n). By carefully storing the values, you can reduce that too to O(1).

    ReplyDelete
  5. calc=a[0]*a[1]*a[2]*a[3]..
    for (int i=0;i<=3;i++)
    b[i]=calc/a[i];

    ReplyDelete