Product Array Puzzle

Given an array \( A \) of \( N \) integers, construct a new array \( B \) such that each element \( B[i] \) is the product of all the elements of \( A \) except \( A[i] \). Formally, for each index \( i \), compute:

\( B[i] = \prod_{\substack{j=0 \\ j \neq i}}^{N-1} A[j] \)

You are not allowed to use the division operation. The array may contain negative numbers. Your solution is expected to run in \( O(N) \) time per test case using a combination of prefix and suffix products.

inputFormat

The input is given via standard input and has the following format:

T
N
A[0] A[1] ... A[N-1]
N
A[0] A[1] ... A[N-1]
... (T test cases in total)

Where:

• T is the number of test cases.
• For each test case, the first line contains the integer \( N \) (the number of elements in the array), and the next line contains \( N \) space-separated integers representing the array \( A \).

outputFormat

For each test case, output a single line containing \( N \) space-separated integers representing the product array \( B \) computed as described above.

1
3
2 3 4

12 8 6