Table of Contents
Problem Statement
In a product array puzzle problem we need to construct an array where the ith element will be the product of all the elements in the given array except element at the ith position.
Example
Input
5
10 3 5 6 2
Output
180 600 360 300 900
Algorithm for solving A Product Array Puzzle
Step 1: Take a vector product to store the products.
a) Initialize it by the vector product
Step 2: Construct two arrays left[] and right[], left stores product of elements up to the left of the ith index in the array. right stores product of elements right of the ith index.
a. Initialize the first element of left as 1 and last element of right as 1.
b. from left, update the ith elements of left array with product of the i-1 th element of given array with the previous element of the left array. (left[i] = left [i-1] * array[i-1]). by doing this, It stores the product till the previous index in the left array from the given array.
c. from right, update the ith elements of right array with the product of the i+1 th element of the given array with the next element of the right array. (right[i] = right[i+1] *array[i+1]). by doing this, It stores the product till the previous index in the left array from the given array.
Step 3: Product except the present element will be same as product of left and right arrays elements.
a) product array will be, product[i] = left[i]*right[i].
Explanation for solving A Product Array Puzzle
First, traverse the array from the beginning and store the product of all previous elements for each i. Now traverse the array from the back and store the sum from the end and store the product of all the elements after that element.
left [] = {10, 30, 150, 900, 1800}
right[] = {1800, 180, 60, 12, 2}
Now using these array find the product of all the elements in the given array except element at the ith position.
product[] = {180, 600, 360, 300, 900}
Implementation
C++ Program for solving A Product Array Puzzle
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int left[n],right[n];
vector<int> product;
left[0] = 1; //initialize the first element as 1
for(int i=1;i<n;i++)
{
left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
}
right[n-1]=1;//initialzie the first element as 1
for(int i=n-2;i>=0;i--)
{
right[i]=right[i+1]*arr[i+1]; //store the product till just next index
}
for(int i=0;i<n;i++)
{
product.push_back(left[i]*right[i]);
}
for(int i=0;i<n;i++)//display the product array
{
cout<<product[i]<<" ";
}
return 0;
}
Java Program for solving A Product Array Puzzle
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
int left[] = new int [n];
int right[] = new int [n];
Vector<Integer> product = new Vector<Integer>();
left[0] = 1; //initialize the first element as 1
for(int i=1;i<n;i++)
{
left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
}
right[n-1]=1;//initialzie the first element as 1
for(int i=n-2;i>=0;i--)
{
right[i]=right[i+1]*arr[i+1]; //store the product till just next index
}
for(int i=0;i<n;i++)
{
product.add(left[i]*right[i]);
}
for(int i=0;i<n;i++)//display the product array
{
System.out.print(product.get(i)+" ");
}
}
}5 10 3 5 6 2
180 600 360 300 900
Complexity Analysis
Time Complexity
O(n) where n is the number of elements present in the array. Here we only traverse 3 times and find the product array.
Space Complexity
O(n) because we use left and right arrays for storing the products of the elements.