We can construct two arrays
P[i] = A[1] * A[2] * ... * A[i],
Q[i] = A[i] *A[i + 1] * ... *. A[n].
in linear time.
thus Ans[i] = P[i - 1] * Q[i + 1].
code like this
// A[1, ..., n] P[0] = Q[n + 1] = 1; for (int i = 1; i = n; i++) { P[i] =
P[i - 1] * A[i]; Q[n - i + 1] = Q[n - i + 2] * A[n - i +
Given an array arr[] of n integers, construct a Product Array prod[]
(of same size) such that prod[i] is equal to the product of all the
elements of arr[] except arr[i]. Solve it without division operator
and in O(n).
Can someone explain me the logic.
Thanks!!
--
You received this message
#includeiostream
using namespace std;
int main()
{
int arr[5]={1,2,3,4,5};
int res[5]={1,1,1,1,1};
int left=1,right=1,i=0;
for(i=0;i5;++i)
{res[i]*=left;
res[4-i]*=right;
left*=arr[i];
right*=arr[4-i];