## We need to construct an array where i^{th}Â element will be the product of all the elements in the given array except element at i^{th}Â position

### Example

**Input array**

Output array element 1: 3 x 5 x 6 x 2

Output array element 2: 10 x 5 x 6 x 2

Output array element 3:Â 10 x 3 x 6 x 2

Output array element 4: 10 x 3 x 5 x 2

Output array element 5: 10 x 3 x 5 x 6

**Output array will be**

## Algorithm

**Time Complexity: O(n)**

**Space Complexity: O(n)**

**Step 1 :** Take a vector product to store the products.

a)Â Â Â Initialize it by vector product

**Step 2 :** Construct two arrays left[] and right[], left stores product of elements upto left of ith index in the array. right stores product of elements right of 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 previous element of 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 product of the i+1 th element of given array with next element of 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].

### Algorithm working Example

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll arr[] = { 10, 3, 5, 6, 2}; //array
int N = sizeof(arr) / sizeof(arr[0]); // size of array
int left[N],right[N]; //arrays to store product upto left of ith index and right of ith index stored in left and right array respectively
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]); // product of the whole array except the current element is same as product of left and right array's ith index
for(int i=0;i<N;i++)//display the product array
cout<<product[i]<<" ";
return 0;
}
```

Normal

0

false

false

false

EN-US

X-NONE

X-NONE