Given an array a[i] of size n, construct a Product Array p (size n) such that p[i] is equal to the product of all the elements of a except a[i].

Example 1:

```Input: a[] = {10, 3, 5, 6, 2}
Output: p[] = {180, 600, 360, 300, 900}
The elements of output array are
{3*5*6*2, 10*5*6*2, 10*3*6*2,
10*3*5*2, 10*3*5*6}```

Example 2:

```Input: a[] = {1, 2, 1, 3, 4}
Output: p[] = {24, 12, 24, 8, 6}
The elements of output array are
{3*4*1*2, 1*1*3*4, 4*3*2*1,
1*1*4*2, 1*1*3*2}```

Example 3:

```input a[] = {12,0,1}
Output p[]: 0 12
{0*1, 12*1 , 12*0}```

approach:

step 1: first traverse through the array and find the product of all the elements in the array and count the number of zeros in the array

step 2: if the number of zero's is equal to 1, than the index in the array a where zero was present should be filled with the product of all elements in the p array.

step 3: else if the number of zero's is greater than 1, all the elements in the p array will be zero.

step 4: else ,if there are no zero's , than all the elements in the p array will be filled with product / a[i]

implementation: in c++

```long long int productExceptSelf(long long int a[], int n)
{
long long int pro=1;
long long int zero=0;
long long int p[n];
for (int i=0;i<n;i++)
{
if(i==0)
zero++;
else
pro=pro*a[i];
}

if(zero==1)
{
for (int i=0;i<n;i++)
{
if(i==0)
p[i]=pro;
else
{
p[i]=0;       }
}
}

else if(zero>1)
{
for (int i=0;i<n;i++)
p[i]=0;
}

else
{
for (int i=0;i<n;i++)
p[i]=(pro/a[i]);   }
}```

time complexity: O(n),because of using a single loop

space complexity:O(n) , because of using an extra array p[]

darkmode