4. Array products

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?

假設ary長度為n, 且被拆成左右兩部分

def products(ary):
  result = []
  for i in range(len(ary)): # n
    ary1 = ary[0:i] # O(1)
    ary2 = ary[i+1:len(ary)] # O(1)
    p1 = p2 = 1
    for j in range(len(ary1)): # x
      p1 *= ary1[j] # O(1)
    for j in range(len(ary2)): # y
      p2 *= ary2[j] # O(1)
    result.append(p1*p2)
  return result

T = n *[ O(1) + O(1) + (O(x) + O(y)) ] # x+ y = n - 1