Product Except Self

Given an array of integers, the task is to construct a new array such that each element at index \(i\) is the product of all the numbers in the original array except the one at \(i\). The challenge is to solve this problem in \(O(n)\) time complexity and without using division.

Example:

Input:  [1, 2, 3, 4, 5]
Output: [120, 60, 40, 30, 24]

It is guaranteed that the product of any prefix or suffix of the array will fit into a 64-bit signed integer.

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array.
The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single line with \(n\) space-separated integers, where the \(i\)-th integer is the product of all the numbers in the array except the one at index \(i\).

5
1 2 3 4 5

120 60 40 30 24