A Product Array Puzzle  

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Apple Asana BlackRock Bloomberg ByteDance Citadel DE Shaw eBay Evernote Expedia Facebook Goldman Sachs Google Houzz Intel LinkedIn lyft Microsoft Morgan Stanley Nutanix Opera Oracle PayPal Paytm Qualtrics Salesforce SAP ServiceNow Snapchat Splunk Tableau Twitter Uber Visa VMware Walmart Labs Yahoo Yandex
Array Groupon LeetCode

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

Please click Like if you loved this article?

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.

See also
Convert array into Zig-Zag fashion

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

See also
Write Code to Determine if Two Trees are Identical

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

Please click Like if you loved this article?

O(n) because we use left and right arrays for storing the products of the elements.

References

Please click Like if you loved this article?