Product of Array Except Self

Given an array of integers \(arr\) of size \(n\), compute an output array \(output\) such that for every index \(i\), \[ output[i] = \prod_{\substack{0 \leq j < n \\ j \neq i}} arr[j] \] without using the division operation.

For example, if \(n = 4\) and \(arr = [1, 2, 3, 4]\), then the output should be [24, 12, 8, 6].

The challenge is to achieve this in \(O(n)\) time with constant extra space (excluding the output array), using a prefix and suffix product approach.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\) which denotes the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array \(arr\).

outputFormat

Output a single line to standard output (stdout) containing \(n\) space-separated integers. The \(i^{th}\) integer should be the product of all elements of the array except \(arr[i]\). Use standard output (stdout) to print your result.

4
1 2 3 4

24 12 8 6