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