question

Given an array A[n] of n numbers, create an output array such that Out[i] is equal to the product of all the elements of A[n] except A[i]. Ex. Out[4] assuming n >= 5 will be the product of the numbers from A[0] through A[3] and the numbers from A[5] through A[n - 1]. Solve this without using the division operator and in O(n).

The value of Out[i] is the product of all numbers before/after Out[i] - separate the solution accordingly.

At each position i in the output array, the value will be the product of all numbers before/after Out[i]. We can get the desired output by using a second array and traversing the input array twice.

In the first iteration, traverse the input array left-to-right and assign Out[i] to the product of all numbers preceding A[i]. Next traverse the array again in the reverse direction and multiply Out[i] by all numbers that followed A[i]. Now each element in Out[] will contain the product of all the elements of A[] except A[i].

Thoughts or alternate solution? Let us know in the comments below!

In the first iteration, traverse the input array left-to-right and assign Out[i] to the product of all numbers preceding A[i]. Next traverse the array again in the reverse direction and multiply Out[i] by all numbers that followed A[i]. Now each element in Out[] will contain the product of all the elements of A[] except A[i].

int[] **productArray**(int[] A, int[] Out) {
int result = 1;
**for** (int i = 0; i < A.size; i++)
{
Out[i] = result;
result *= A[i];
}
result = 1;
**for** (int i = A.size - 1; i >= 0; i--)
{
Out[i] *= result;
result *= A[i];
}
**return** Out;
}

Thoughts or alternate solution? Let us know in the comments below!