Product of all numbers except self

Companies:
  • Adobe Interview Questions
  • Amazon Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Goldman Sachs Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions
  • Nutanix Interview Questions
  • Oracle Interview Questions

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;
}
Scroll to Top