# Product array puzzle -searching|sorting

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[]