leetcode_238

gistfile1.txt

// Explanation
//    0 1 2 3 4
// 0 |  o o o o|
// 1 |o   o o o|
// 2 |o o   o o|
// 3 |o o o   o|
// 4 |o o o o  |
//
// Goal is to "sum up" the dots in each columns. (Dot represents a product of course not a sum)
// I do that by first "summing up" the upper triangle, then the lower triangle

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {        
        vector<int> ret(nums.size(), 1);
        int acc = 1;
        for (int i = 0; i < nums.size() - 1; ++i) {
            acc *= nums[i];
            ret[i + 1] *= acc;
        }
        acc = 1;
        for (int i = nums.size() - 1; i > 0; --i) {
            acc *= nums[i];
            ret[i - 1] *= acc;
        }
        return ret;
    }
};