Discussion on: Daily Coding Problem #2

[Benjamin Braatz]

Solution in Python without division, still in O(n²), but inner loop is only executed n²/2 times:

def prod(input):
    output = []
    product = 1
    for number in input:
        for i in range(len(output)):
            output[i] *= number
        output.append(product)
        product *= number
    return output