(C++)Simple code using logarithm space


  • 1
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> &input = nums;
            int n = nums.size();
            vector<int> output(n);
            int numOfZero = 0, prod = 1, sign = 1, posOfZero;
    	for(int  i = 0; i < n; i++){
    		if(input[i] == 0) {
    			numOfZero ++;
    			if(numOfZero == 2) break;
    			posOfZero = i;
    		}
    		else{
    			prod *= input[i];
    			if(input[i] < 0) sign *= -1;
    		}
    	}
    
    	if(numOfZero >= 2){
    		for(int i = 0; i < n; i++) output[i] = 0;
    	}
    
    	else if(numOfZero == 1){
    		for(int i = 0; i < n; i++){
    			output[i] = 0;
    		}
    		output[posOfZero] = prod;
    	}
    
    	else{
    	prod = abs(prod);
    	double logProd = log2(prod);
    	for(int i = 0; i < n; i++){
    		double logAnsi = logProd - log2(abs(input[i]));
    		double approxAnsi = pow(2, logAnsi);
    		int _ansi = (int) approxAnsi;
    		if(approxAnsi - _ansi > 0.5) _ansi ++;
    		output[i] = sign * ( (input[i] > 0)? 1 : -1 ) * _ansi;
    	}
    	}
    	return output;
    
        }
        };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.