How to get it working in O(n)? [duplicate]

Question

Possible Duplicate:
Interview Q: given an array of numbers, return array of products of all other numbers (no division)

I came across an interview task/question that really got me thinking ... so here it goes:

You have an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

I really tried to come up with a solution but I always end up with a complexity of O(n^2). Perhaps the is anyone smarter than me who can tell me an algorithm that works in O(n) or at least give me a hint...

Answer 1

Construct two temporary arrays - B[N] and C[N]. Form each element of B[N] as the product of the A[N] elements to its left (including itself) - working left to right, N operations. Form each element of C[N] as the product of the A[N] elements to its right (including itself) - working right to left, N operations.

Then A[n] = B[n-1] * C[n+1] - another N operations to work this out. You end up with just short of 3N operations, which is O(N). It's just short, because B[0] and C[N-1], and the first and last A, don't require multiplication. Also, C[0] = B[N-1], so I think you should need exactly 3N-5 operations.