Day 15 of 30-Day LeetCode Challenge

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Note: Please solve it without division and in O(n)

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {

int n = nums.size();

//method 1 : use 2 extra array -> 75%
//O(n) time & O(n) space
// vector<int> preProduct(n, 1);
// vector<int> postProduct(n, 1);

// //arrays is traversed 3n times
// for(int i=1;i<n;++i) preProduct[i] = preProduct[i-1]*nums[i-1];
// for(int i=n-2;i>=0; — i) postProduct[i] = postProduct[i+1]*nums[i+1];

// vector<int> result;
// for(int i=0;i<n;++i){
// result.push_back(preProduct[i]*postProduct[i]);
// }
// return result;

//method 2 : 2 extra arrays are combined into result array -> 96%
vector<int> result(n, 1);
for(int i=1;i<n;++i) result[i] *= (result[i-1]*nums[i-1]);
int temp = 1;
for(int i=n-2;i>=0; — i) {
result[i] *= (temp*nums[i+1]);
temp *= nums[i+1];
}
return result;

//method 3 : using logarithms
//NOTE :- won’t work for cases where elements maybe 0 since log 0 is undefined
// long double log_sum = 0; //stores sum of all log(x) where x is every element in array
// for(int i=0;i<n;++i) log_sum += (long double)log10(nums[i]);
// vector<int> result;
// for(int i=0;i<n;++i){
// long double log_sum_except_current = log_sum — (long double)log10(nums[i]);
// result.push_back((int)(EPS+pow((long double)10.00, log_sum_except_current)));
// }
// return result;

}
};