algorithms

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

min-ops-to-reduce-x-to-zero.cpp (847B)


      1 class Solution {
      2 public:
      3     int minOperations(vector<int>& nums, int x) {
      4         unordered_map<int,int> prefixSum{};
      5 
      6         int sum = 0;
      7         for(int i = 0; i < nums.size(); ++i) {
      8             prefixSum[sum] =  i;
      9             sum += nums[i];
     10         }
     11 
     12         prefixSum[sum] = nums.size();
     13         
     14         int minNum = 1000000;
     15 
     16         if(sum < x) {
     17             return -1;
     18         }
     19         for(auto& val: prefixSum) {
     20             int target = val.first + (sum - x);
     21             if(prefixSum.find(target) != prefixSum.end()) {
     22                 minNum = min(
     23                     (int)(nums.size() - (abs(prefixSum[target] - prefixSum[val.first]))),
     24                     minNum
     25                 );
     26             }
     27         }
     28 
     29         if(minNum == 1000000) {
     30             return -1;
     31         } else {
     32             return minNum;
     33         }
     34 
     35     }
     36 };