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 };