Puzzle.. solving product of values in array X

Question

Hello,

Can you please help me solving this one?

You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi. You may not use division. You can use extra memory. (Hint: There are solutions faster than O(n^2).)

The basic ones - O(n^2) and one using division is easy. But I just can't get another solution that is faster than O(n^2).

Answer 1

Let left[i] be the product of all elements in X from 1..i. Let right[i] be the product of all elements in X from i..N. You can compute both in O(n) without division in the following way: left[i] = left[i - 1] * X[i] and right[i] = right[i + 1] * X[i];

Now we will compute M: M[i] = left[i - 1] * right[i + 1]

Note: left and right are arrays.

Hope it is clear:)

Answer 2

Here's a solution in Python. I did the easy way with division to compare against the hard way without. Do I get the job?

L = [2, 1, 3, 5, 4]

prod = 1
for i in L: prod *= i
easy = map(lambda x: prod/x, L)
print easy

hard = [1]*len(L)
hmm = 1
for i in range(len(L) - 1):
    hmm *= L[i]
    hard[i + 1] *= hmm
huh = 1
for i in range(len(L) - 1, 0, -1):
    huh *= L[i]
    hard[i - 1] *= huh
print hard