Online Judge Solutions

Tuesday, December 30, 2014

Product of Array Exclude Itself

Given an integers array A.
Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], calculate B without divide operation.
Example
For A=[1, 2, 3], B is [6, 3, 2]
   vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n);
        
        long long left =1;
        for(int i = 0; i < n; i++) {
            output[i] = left; 
            left *= nums[i];
        }
        
        long long right = nums[n-1];
        for(int i = n-2; i >=0; i--){ 
            output[i] *= right; 
            right *= nums[i];
        }
        
        return output;
    }
vector<long long> productExcludeItself(vector<int> &nums) {
        int n = nums.size();
        vector<long long> output1;
        if (n < 2) return output1;
        
        vector<long long> output(n, 1);
        
        long long left =1, right = 1;
        for(int i = 0; i < n; i++) {
            output[i] *= left; 
            left *= nums[i];
            
            output[n-1-i] *= right;
            right *= nums[n-1-i];
        }
        
        return output;
    }

No comments:

Post a Comment