You are given an array containing n integers (n>1), you need to return an output array such that output [i] is equal to the product of all the elements of the array except the i’th element.
Input: [1, 2, 3, 4] Output: [24, 12, 8, 6]
Constraint: You need to solve the problem without using division operator and in O(n) time complexity.
Algorithm:
- Build two arrays left and right of the same size as that of the input array. Initialize left [0] with array [0] and right [n-1] with array [n-1].
- Loop for i = 1 to (n-1), and in each iteration set left [i] = array [i] * left [i-1]. This means that left [i] contains the product of all elements to the left of i’th element in the array alongwith the current element.
- Loop for i = (n-2) to 0, and in each iteration set right [i] = right [i+1] * array [i]. This means that right [i] contains the product of all elements to the right of i’th element in the array alongwith the current element.
- Now, create another vector output of the same size. Loop for i = 0 to (n-1), and in each iteration, do the following.
If i = 0, set output [i] = right [i+1] {product if all elements to the right of 0’th element}. If i = (n-1), set output [i] = left [i-1] {product of all elements to the left of (n-1)’th element}. For all other values of i, set output [i] = right [i+1] * left [i-1].
For a better understanding, look at the code below.
#include <bits/stdc++.h> using namespace std; vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> left(n); vector<int> right(n); left[0] = nums[0]; right[n-1] = nums[n-1]; for(int i=1; i<left.size(); i++){ left[i] = nums[i]*left[i-1]; } for(int i = n-2; i>=0; i--){ right[i] = nums[i]*right[i+1]; } vector<int> res(n); for(int i=0; i<nums.size(); i++){ if(i==0){ res[i] = right[i+1]; }else if(i==nums.size()-1){ res[i] = left[i-1]; }else{ res[i] = right[i+1]*left[i-1]; } } return res; } int main(){ vector <int> nums = {1, 2, 3, 4}; vector <int> output = productExceptSelf(nums); for(auto i:output){ cout<<i<<" "; } return 0; }
Also, check out another popular interview problem Find pivot index.
One comment