How to make it work in O (n)?

Question

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

I came across an interview task / question that really made me think ... so here it is:

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

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

Answer 1

Create two temporary arrays - B [N] and C [N]. Form each element B [N] as a product of elements A [N] to the left (including itself) - working from left to right, N operations. Form each element C [N] as a product of elements A [N] from the right (including yourself) - we work from right to left, N operations.

Then A [n] = B [n-1] * C [n + 1] is another N operations for this. As a result, you get only 3N operations, that is, O (N). It is simply short, because B [0] and C [N-1], as well as the first and last A, do not require multiplication. Also, C [0] = B [N-1], so I think you only need 3N-5 operations.

Answer 2

You create 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] . They can be generated in O (n). Your output value B[i] will be just L[i] * U[i] - again this is O (n).

Answer 3

Deception, which 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] } }