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




darkmode