algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

product-of-array-except-self.cpp (1019B)

      1 class Solution {
      2 public:
      3     vector<int> productExceptSelf(vector<int>& nums) {
      4         
      5         vector<int> prefix_product (nums.size());
      6         vector<int> suffix_product (nums.size());
      7 
      8         int prefix_prd = 1;
      9         int suffix_prd = 1;
     10 
     11         for(size_t i = 0; i < nums.size(); ++i) {
     12             
     13             prefix_product[i] = prefix_prd;
     14 
     15             int inv = (nums.size() - 1) - i;
     16             suffix_product[inv] = suffix_prd;
     17 
     18             if (i < nums.size()) {
     19                 prefix_prd *= nums[i];
     20             }
     21 
     22             if (inv >= 0 && inv < nums.size()) {
     23                 suffix_prd *= nums[inv];
     24             }
     25 
     26 
     27         }
     28 
     29         vector<int> results (nums.size());
     30         for(size_t i = 0; i < nums.size(); ++i) {
     31             int res = 1;
     32             if(i > 0) {
     33                 res *= prefix_product[i];
     34             }
     35             if(i + 1 < nums.size()) {
     36                 res *= suffix_product[i];
     37             }
     38 
     39             results[i] = res;
     40         }
     41         return results;
     42     }
     43 };