Product of Array Except Self

Given an array of integers \(A = [a_1,a_2,...,a_n]\), the task is to compute a new array \(B\) where each element \(B[i]\) is the product of all elements in \(A\) except \(A[i]\). You are not allowed to use division in your solution and your algorithm should run in \(O(n)\) time complexity.

For example, if \(A = [1, 2, 3, 4]\), then the result should be \([24, 12, 8, 6]\) because:

• \(B[0] = 2 \times 3 \times 4 = 24\)
• \(B[1] = 1 \times 3 \times 4 = 12\)
• \(B[2] = 1 \times 2 \times 4 = 8\)
• \(B[3] = 1 \times 2 \times 3 = 6\)

This problem is intended to test your understanding of prefix and suffix product calculations.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers representing the array \(A\). For example:

4
1 2 3 4

outputFormat

The output should be printed to standard output (stdout) as a single line containing \(n\) space-separated integers representing the resulting array \(B\). For the above input, the correct output is:

24 12 8 6

4
1 2 3 4

24 12 8 6