Product Of Array Except Self Problem Statement

You are provided with an integer array ARR of size N. You need to return an array PRODUCT such that PRODUCT[i] equals the product of all the elements of ARR except ARR[i].

Example:

Input:

T = 2
N = 4
ARR = [1, 2, 3, 4]
N = 3
ARR = [2, 3, 4]

Output:

[24, 12, 8, 6]
[12, 8, 6]

Constraints:

1 ≤ T ≤ 100

0 ≤ N ≤ 10⁵

0 ≤ ARR[i] ≤ 10⁵

Time Limit: 1 sec

Note:

Each product may exceed integer limits, so take modulo MOD = 10⁹ + 7 to keep results in bounds.

Follow Up:

Can you solve the problem using O(1) additional space?

Question

Product Of Array Except Self Problem Statement

You are provided with an integer array ARR of size N. You need to return an array PRODUCT such that PRODUCT[i] equals the product of all the elements of ARR except ARR[i].

Example:

Input:

T = 2
N = 4
ARR = [1, 2, 3, 4]
N = 3
ARR = [2, 3, 4]

Output:

[24, 12, 8, 6]
[12, 8, 6]

Constraints:

1 ≤ T ≤ 100
0 ≤ N ≤ 10⁵
0 ≤ ARR[i] ≤ 10⁵
Time Limit: 1 sec

Note:

Each product may exceed integer limits, so take modulo MOD = 10⁹ + 7 to keep results in bounds.

Follow Up:

Can you solve the problem using O(1) additional space?

Accepted Answer

The problem requires returning an array where each element is the product of all elements in the input array except itself.

Iterate through the array twice to calculate the product of all elements to the left and right of each element.
Use two arrays to store the products of elements to the left and right of each element.
Multiply the corresponding elements from the left and right arrays to get the final product array.
Handle integer overflow by taking modulo MOD = 10^9 + 7.
To solve with O(1) additional space, reuse the output array to store the left and right products.

Asked in Accenture