Product of Array Except Self LeetCode Solution

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

Link: https://leetcode.com/problems/product-of-array-except-self/

Solution in C++ #

class Solution { public: vector productExceptSelf(vector& a) { vector ans;

    // using ans vector as left product list
    ans.push\_back(1);
    for(int i=1; i<a.size(); i++) {
        ans.push\_back(a\[i-1\] \* ans\[i-1\]);
    }
    
    int r = 1;
    for(int i=a.size()-1; i>=0; i--) {
        ans\[i\] = ans\[i\] \* r;
        r = r \* a\[i\];
        // calculating the right product on the fly
    }
    
    return ans;        
}

};