No division operator and O(n)

Some site said that this is a google interview question:

There is an array A[N] of N integers. You have to compose an array B[N] such that B[i] will be equal to the product of all the elements of A[] except A[i].

B[i] = (product from j = 1 to N, j not equal to i) A[i]

Example:

Input:[4, 3, 2, 1, 2]
Output:[12, 16, 24, 48, 24]

Solve it without division operator and in O(n).

Update (11/12/09) : Solution provided by Subhasis (EE, IITB) in comments!!
Update (01/01/10) : Solution for another case provided by Shantanu Gangal, BCG (CSE, IITB alumnus) in comments!!

Comments

  1. scan the list starting from 1 to get the partial products of the first n-1 terms in another array B[n]. Then scan from the end to get the partial sums of the n-1 last terms in another array C[n]. Then the answer = B[n]*C[n]

    ReplyDelete
  2. could you elaborate on the solution a little bit? what exactly is stored in B[i] and C[i]?

    ReplyDelete
  3. To make things simpler.. Lets say I make two arrays L[i] and R[i]
    where L[i] = Product of all elements left to i in A

    So, A = [4,3,2,1,2]
    Then, L = [1,4,12,24,24]

    Similarly, R[i] is product of all elements to the right of i in A
    R = [12,4,2,2,1]

    Note that L and R can be calculated in O(n)

    So, B[i] = L[i]*R[i] can be calculated in O(n)

    B = [12, 16, 24, 48, 24]

    Hope that helps!

    ReplyDelete
  4. Can we be cheeky & use the log / antilog operators :P ?

    If yes,
    C[i] = log(A[i]) & E = sum(C[i])
    B[i] = antilog(E - C[i])

    ReplyDelete
  5. If they disallow the cheek,
    Then;
    C[i] = {j=1 to i-1}Product(A[j])
    D[i] = {j=i+1 to n}Product(A[j])

    and B[i] = C[i]*D[i]

    Since,
    C[j] = C[j-1]*A[j-1] &
    D[j] = D[j+1]*A[j+1]; all computations are O(n)

    ReplyDelete
  6. @Shantanu..
    Interesting solution using log and anti-log operations :P Thanx.

    In both cases (cheek allowed or not), correct solution. Thanx.

    ReplyDelete
  7. @Pratik

    How is L[i] O(n)?

    For each element it is looping through the list to the right, so as such there are 2 loops, i.e. O(n^2)

    Actually a simpler solution instead of doing separate L[i] and R[i] would be to start from 0 to n-1 and skip i, but it would still be O(n^2).

    :(

    ReplyDelete
  8. @Eco-nemesis,

    For L(i) i from 1 to n , we do not need to loop through the n entries of A.

    L(i) = A(1)..A(i) = L(i-1)*A(i)
    and so L(i) for all n values can be calculated in O(n)

    ReplyDelete
  9. Ah, now I got it ... I had missed the part where you use the previous value of i-1.

    Cool.

    ReplyDelete

Post a Comment