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;
}