18 July 2008

Google challenge

From the Ruby Forum: http://www.ruby-forum.com/topic/156473#new

There is an array A[N] of N integers. You have to compose an array Output[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Note: Solve it without the division operator and in O(n).
Here is my Python version. Note any difference between this implementation and those discussed in the Ruby Forum?

# http://www.ruby-forum.com/topic/156473#new
_input = [4, 3, 2, 1, 2]

after = []
before = []

t = 1
for x in _input:
    before.append(t) 
    t *= x

t = 1
for x in reversed(_input):
    after.append(t)
    t *= x
after.reverse()

for x, y in zip(before, after):
    print x * y