Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N]
That means each entry in the product array should contain product off all the elements except the one at that particular index.
For example let us consider the array [4, 2, 10, 5], the output should be {100, 200, 40, 80}.
The restriction here is that we have to device an algorithm without using division operation. Had it been allowed, we would have simply calculated the product of all the elements and fill the product array by dividing this with the current element.
Here is the solution approach.
We do this using two iterations one forward and the other backward.
- In the forward iteration, we fill the product array by filling each entry with product of all the elements before it.
- In the backward iteration, we multiply each element with product of all the elements to the right of it.
Here is the C++ implementation for this. The time complexity is O(n).