Product Except Self

Given an array of integers, your task is to compute 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. More formally, if the original array is \(nums[0 \dots n-1]\), then for every valid index \(i\), the answer is defined as:

\[ answer[i] = \prod_{\substack{0 \leq j < n \\ j \neq i}} nums[j] \]

Note that your solution must run in O(n) time and with O(n) additional space, and the use of division is not allowed.

inputFormat

The first line contains a single integer n (0 ≤ n ≤ 10⁵), denoting the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single line containing n space-separated integers, where the i-th integer is the product of all the numbers in the input array except the number at index i.

4
1 2 3 4

24 12 8 6