Given an array ` arr `

of ` n `

integers, print an array ` answer `

such that ` answer[i] `

is equal to product of all elements in ` arr `

except ` arr[i] `

.

You should do this problem in ` O(n) `

time complexity and without using ` division `

## Example Test Cases

### Sample Test Case 1

Input Array: ` [2, 3, 4, 5] `

Expected Output: ` [60, 40, 30, 24 ] `

Explanation: ` answer[0] = arr[1]*arr[2]*arr[3] `

, ` answer[1] = arr[0]*arr[2]*arr[3] `

and ` answer[2] = arr[0]*arr[1]*arr[3] `

and ` answer[3] = arr[0] * arr[1] * arr[2] `

## Solution

To solve this problem, let us define two arrays ` left `

and ` right `

of size ` n `

, such that

` left[i] = arr[0]*arr[1]*arr[2]...arr[i-1] `

and

` right[i] = arr[i + 1]*arr[i + 2]*arr[i + 3]*arr[i + 4]*....arr[n-1]`

We want to compute ` answer[i] `

for each value of ` i `

We know that ` answer[i] = (arr[0]*arr[1]*arr[2]*...arr[i-1])*(arr[i+1]*arr[i + 2]*arr[i + 3]*arr[i + 4]....arr[n-1]) `

Therefore, using the above three equations we can rewrite ` answer[i] `

as ` answer[i] = left[i] * right[i] `

Therefore, we can compute arrays ` left `

and ` right `

in one loop and then compute the array ` answer `

as shown below.

### Computing Left Array

### Computing Right Array

### Computing Final Answer after multiplying left and right array

## Solution Implementation

#include <iostream> #include <vector> using namespace std; vector<int> getProduct(vector<int>& arr) { int n = arr.size(); vector<int> left(n), right(n), answer(n); left[0] = 1; right[n - 1] = 1; for(int i = 1; i < n; i++) { left[i] = left[i-1]*arr[i-1]; right[n - i - 1] = right[n-i]*arr[n - i]; } for(int i = 0; i < n; i++) { answer[i] = left[i] * right[i]; } return answer; } int main() { vector<int> arr = { 2, 3, 4, 5 }; vector<int> answer = getProduct(arr); for(int i = 0; i < arr.size(); i++) cout << answer[i] << " "; cout << "\n"; return 0; }