Product of Array Except Self - Medium - L
Published:
Question
- https://leetcode.com/problems/product-of-array-except-self/
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Approach
- First is product approach maintaining left and right arrays.
- Use log and antilog
Solution
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> left(n,1);
vector<int> right(n,1);
if (n==0) {
return nums;
}
left[0]=1;
right[n-1]=1;
for(int i=1;i<n;i++) {
left[i]=left[i-1]*nums[i-1];
}
for(int i=n-2;i>=0;i--) {
right[i]=right[i+1]*nums[i+1];
}
for(int i=0;i<n;i++) {
nums[i]=left[i]*right[i];
}
return nums;
}
};