How to get it working in O(n)?

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.

Answer 2

You generate two intermediate arrays, L, where L[i] = products of A[0]..A[i-1], and U where U[i] = products of A[i+1]..A[N-1]. These can both be generated in O(n). Your output value B[i] will just be L[i] * U[i] - again this is O(n).

Answer 3

Cheating I know but:-

for (x = 0 ; x < n ; x++) {
   bigtot = bigtot * in[x];
}
for (x = 0 ; x < n ; x++) {
      out[n] = bigot;
      for ( y = in[x]; y > 0 ; y--) {
         out[n] = out[n] - in[x]
      } 
}