# C++ Program to find the product array puzzle

Write a C++ program to form a product array from arr[] where product[i] is the product of all the array elements except arr[i].

Example

Input: arr[]  = {10, 3, 5, 6, 2}

Output: prod[]  = {180, 600, 360, 300, 900}

Prod[0] = 3 * 5 * 6 * 2 product of other array elements except 10 is 180

Prod[1] = 10 * 5 * 6 * 2 product of other array elements except 3 is 600

Prod[2] = 10 * 3 * 6 * 2 product of other array elements except 5 is 360

Prod[3] = 10 * 3 * 5 * 2 product of other array elements except 6 is 300

Prod[4] = 10 * 3 * 6 * 5 product of other array elements except 2 is 900

Input: arr[]  = {1, 2, 3, 4, 5}

Output: prod[]  = {120, 60, 40, 30, 24 }

Prod[0] =2 * 3 * 4 * 5  product of other array elements except 1 is 120

Prod[1] =1 * 3 * 4 * 5  product of other array elements except 2 is 60

Prod[2] =1 * 2 * 4 * 5  product of other array elements except 3 is 40

Prod[3] =1 * 2 * 3 * 5  product of other array elements except 4 is 30

Prod[4] =1 * 2 * 3 * 4  product of other array elements except 5 is 24

### Brute force approach

Create two arrays left[] and right[] in such a way that -

• Left[] - stores the product of the array elements from the start to that index.
• Right[] - stores the product of the array from the last to that index.

Now, to get the product array we multiply the left product upto i-1 and the right product to i+1. This will exclude the current ith element that is also the requirement.

Algorithm

• Create three arrays - left, right, and product.
• Iterate from 0 to n and update left as

left[i] = arr[i - 1] * left[i - 1]

• Update the right array as by running the loop from n-1 to 0

right[j] = arr[j + 1] * right[j + 1]

• Run a loop from 0 to n and update the prod array by multiplying the left and right array.

prod[i] = left[i] * right[i]

• Print the prod array.

C++ code

`#include <bits/stdc++.h>using namespace std;void productArray(int arr[], int n) // function to find the product array{          // if the array size is 1 no product array  can be formed          if (n == 1) {                   cout << 0;                   return;          }          // make the left and right array          int* left = new int[sizeof(int) * n];          int* right = new int[sizeof(int) * n];          // make the resultant product array          int* prod = new int[sizeof(int) * n];          int i, j;          // as left will be multiplied with other indicies the first product is 1          left[0] = 1;// as right will also be multiplied with other indicies the last product is 1          right[n - 1] = 1;// fill the left array          for (i = 1; i < n; i++)                   left[i] = arr[i - 1] * left[i - 1];          // fill the right array          for (j = n - 2; j >= 0; j--)                   right[j] = arr[j + 1] * right[j + 1];// multiply left and right to form product array          for (i = 0; i < n; i++)                   prod[i] = left[i] * right[i];// print the formed product array          for (i = 0; i < n; i++)                   cout << prod[i] << " ";          return;}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay          cout << "The resultant array: \n";          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`

C code

`#include <stdio.h>#include <stdlib.h>void productArray(int arr[], int n) // function to find the product array{          // if the array size is 1 no product array  can be formed          if (n == 1) {                   printf("0") ;                   return;          }          // make the left and right array int* left = (int*)malloc(sizeof(int) * n);    int* right = (int*)malloc( sizeof(int) * n);          // make the resultant product array   int* prod = (int*)malloc(sizeof(int) * n);          int i, j;          // as left will be multiplied with other indicies the first product is 1          left[0] = 1;// as right will also be multiplied with other indicies the last product is 1          right[n - 1] = 1;// fill the left array          for (i = 1; i < n; i++)                   left[i] = arr[i - 1] * left[i - 1];          // fill the right array          for (j = n - 2; j >= 0; j--)                   right[j] = arr[j + 1] * right[j + 1];// multiply left and right to form product array          for (i = 0; i < n; i++)                   prod[i] = left[i] * right[i];// print the formed product array          for (i = 0; i < n; i++)                   printf("%d ",prod[i]);          return;}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay          printf( "The resultant array: \n");          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`

Time complexity - O(n)

Space complexity - O(n)

### Efficient solution

In the previous approach, we created left and right arrays. So, here we will minimise the space by only using the product array itself.

• Create a prod array with all the indices as value 1.
• Create a temp variable and set its value to 1
• For every index, update prod[i] to temp and then update temp by

temp = temp * prod[i]

• Repeat the above step by iterating from last to 0. Now, set

prod[i]* = temp and then temp* = arr[i]

• Print the prod array.

C++ code

`#include <bits/stdc++.h>using namespace std;void productArray(int arr[], int n){          // if the array size is 1 no product array  can be formed          if (n == 1) {                   cout << 0;                   return;          }int i, temp = 1;    int* prod = new int[(sizeof(int) * n)]; // Allocate resultant prod array       memset(prod, 1, n); // set all values in prod array as 1    /* In this loop, temp variable contains product of       elements on left side excluding arr[i] */    for (i = 0; i < n; i++) {        prod[i] = temp;        temp *= arr[i];    }    //Initialize temp to 1for product on right side    temp = 1;    //In this loop, temp variable contains product of      // elements on right side excluding arr[i]    for (i = n - 1; i >= 0; i--) {        prod[i] *= temp;        temp *= arr[i];    }    // print prod array    for (i = 0; i < n; i++)        cout << prod[i] << " ";    return;}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay    cout <<  "The resultant array: \n";          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`

C code

`#include <stdio.h>#include <stdlib.h>void productArray(int arr[], int n){          // if the array size is 1 no product array  can be formed          if (n == 1) {                   printf("0");                   return;          }int i, temp = 1;          // make the resultant product array   int* prod = (int*)malloc(sizeof(int) * n);    memset(prod, 1, n); // set all values in prod array as 1    /* In this loop, temp variable contains product of       elements on left side excluding arr[i] */    for (i = 0; i < n; i++) {        prod[i] = temp;        temp *= arr[i];    }    //Initialize temp to 1for product on right side    temp = 1;    //In this loop, temp variable contains product of      // elements on right side excluding arr[i]    for (i = n - 1; i >= 0; i--) {        prod[i] *= temp;        temp *= arr[i];    }    // print prod array    for (i = 0; i < n; i++)        printf("%d ",prod[i]);    return;}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay    printf( "The resultant array: \n");          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`

## Another approach

The approach first takes the product of the whole array variables. After that iterate in the array and update the index of arr[i] as

arr[i] = prod/arr[i]

And then return the new array.

C++ code

`#include <iostream>using namespace std;void productArray(int a[], int n){          long prod = 1; // the product is assigned as 1          long flag = 0; // to track 0's in the array          // Calculate the product of all elements          for (int i = 0; i < n; i++) {                   if (a[i] == 0) // increment flag if there is any 0                             flag++;                   else                             prod *= a[i]; // calculate prod          }          long* arr = new long[n]; // create resultant arr          for (int i = 0; i < n; i++) {                   if (flag > 1) { // if the count of flag is > 0 then                             arr[i] = 0; // all element in array are 0                   }                   else if (flag == 0) // if no zero encountered in arr[i]                             arr[i] = (prod / a[i]);                   // if 1 element of array having                   // value 0 than all                   // the elements except that index                   // value , will be                   // equal to 0                   else if (flag == 1 && a[i] != 0) {                             arr[i] = 0;                   }                   // if(flag == 1 && a[i] == 0)                   else                             arr[i] = prod;          }          for(int i=0;i<n;i++)          cout << arr[i] << " ";}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay    printf( "The resultant array: \n");          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`

C code

`#include <stdio.h>#include <stdlib.h>void productArray(int a[], int n){                   long prod = 1; // the product is assigned as 1          long flag = 0; // to track 0's in the array          // Calculate the product of all elements          for (int i = 0; i < n; i++) {                   if (a[i] == 0) // increment flag if there is any 0                             flag++;                   else                             prod *= a[i]; // calculate prod          }          // make the resultant product array   long* arr = (long*)malloc(sizeof(long) * n);          for (int i = 0; i < n; i++) {                   if (flag > 1) { // if the count of flag is > 0 then                             arr[i] = 0; // all element in array are 0                   }                   else if (flag == 0) // if no zero encountered in arr[i]                             arr[i] = (prod / a[i]);                   // if 1 element of array having                   // value 0 than all                   // the elements except that index                   // value , will be                   // equal to 0                   else if (flag == 1 && a[i] != 0) {                             arr[i] = 0;                   }                   // if(flag == 1 && a[i] == 0)                   else                             arr[i] = prod;          }          for(int i=0;i<n;i++)          printf("%d ", arr[i]);}int main(){          int arr[] = { 10, 3, 5, 6, 2 };          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay    printf( "The resultant array: \n");          productArray(arr, n);}`

Output

`The resultant array:180 600 360 300 900`