"""
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 findProduct(arr):

    arrLen = len(arr)

    if arrLen == 0:
        return 0

    leftArr = [None] * arrLen
    rightArr = [None] * arrLen
    resultArr = [None] * arrLen
    
    leftArr[0] = 1
    rightArr[-1] = 1
    
    # Forward pass for left products
    for i in range(1, arrLen):
        leftArr[i] = leftArr[i-1] * arr[i-1]
    
    # Backward pass for right products
    for i in range(len(array)-2, -1, -1):
        rightArr[i] = rightArr[i+1] * arr[i+1]

    for i in range(arrLen):
        resultArr[i] = leftArr[i] * rightArr[i]

    return resultArr


array = [1, 2, 3, 4, 5]
resultArray = findProduct(array)
print(resultArray)



