Tuesday, May 12, 2015

[LintCode] 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 BWITHOUT divide operation.
Example
For A=[1, 2, 3], return [6, 3, 2].
class Solution {
public:
    vector<long long> productExcludeItself(vector<int> &nums) 
    {
        int n = nums.size();
        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;
    }
};