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 LeetCodeViews 4997

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.

References

Translate »