# coding: utf-8
# Your code here!

#Good morning! Here's your coding interview problem for today.

#This problem was asked by Uber.

#Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

#For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

#Follow-up: what if you can't use division?


def other_products(ls):
    leaf_cnt = len(ls)
    hp = [ 1 for x in range(0,leaf_cnt-1) ] + ls

    def parent(i):
        return (i - 1) // 2

    for r in range( len(hp) - 1, 0, -2 ):
        hp[parent(r)] = hp[r]*hp[r-1]

    def sibling(i):
        if i % 2 == 0:
            return i - 1
        else:
            return i + 1
    def compute_product(i):
        result = 1
        while i != 0:
            result *= hp[sibling(i)]
            i = parent(i)
        return result

    #return compute_product(len(ls))
    return [ compute_product( len(ls) - 1 + i  ) for i in range(0,len(ls)) ]



#print( other_products( [1, 2, 3, 4, 5]) )
assert( other_products( [1, 2, 3, 4, 5]) ==  [120, 60, 40, 30, 24] )
assert( other_products( [3, 2, 1]) ==  [2, 3, 6] )
print ( "OK" )