Facebook
From Sole Rhinoceros, 4 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 112
  1. class Solution {
  2. public:
  3.     vector<int> productExceptSelf(vector<int>& nums) {
  4.         // Compute the Suffix Array
  5.         // Preprocessing stage
  6.         int n = nums.size(), p = 1, i;
  7.         // Declare an integer array of size n
  8.         vector<int> suff(n, 0);
  9.        
  10.         for(i = n-1; i >= 0; i--){
  11.             p = p*nums[i];
  12.            
  13.             suff[i] = p;
  14.         }
  15.        
  16.         // Actual computation
  17.         // Declare the result array
  18.         vector<int> res(n, 0);
  19.        
  20.         p = 1;
  21.         for(i = 0; i < n-1; i++){
  22.             res[i] = p*suff[i+1];
  23.            
  24.             p = p*nums[i];
  25.         }
  26.        
  27.         res[n-1] = p;
  28.        
  29.         return res;
  30.        
  31.        
  32.     }
  33. };