Home » Technical Interview Questions » Array Interview Questions » A Product Array Puzzle

A Product Array Puzzle


Reading Time - 4 mins

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

READ  Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

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}

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;
}
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.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions