"""
Computes product of array except self.
nums = input list
returns a new list containing the result
"""
def product_except_self(nums):
size = len(nums)
answer = [0] * size # allocate output list
prefix = 1
# ---- Prefix products ----
# answer[i] gets product of all elements before i
for i in range(size):
answer[i] = prefix # store prefix product
prefix *= nums[i] # update prefix
# Example for nums = [5,2,3,4]:
# prefix values: 1, 5, 10, 30
# ---- Suffix products ----
# Multiply each answer[i] by product of all elements after i
suffix = 1
for i in range(size - 1, -1, -1):
answer[i] *= suffix # combine prefix * suffix
suffix *= nums[i] # update suffix
# suffix values: 1, 4, 12, 24, 120
# final answer: 24, 60, 40, 30
# 24 (24*1) 60 (12*5) 40 (10*4) 30 (30*1)
return answer
def main():
arr = [5, 2, 3, 4]
result = product_except_self(arr)
print("Result:", *result)
if __name__ == "__main__":
main()
"""
run:
Result: 24 60 40 30
"""
