In a product array puzzle problem we need to construct an array where the i^{th} element will be the product of all the elements in the given array except element at the i^{th} 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 i^{th} 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.