aboutsummaryrefslogtreecommitdiff
path: root/min_operations_x_zero.cpp
blob: 011839e279a4b4826d10ab20d4a6434a11a32bbf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "leetcode.h"

class Solution {
public:
  int minOperations(vector<int> &nums, int x) {
    unordered_map<int, int> left;
    int ans = INT_MAX;
    for (auto i = 0, sum = 0; i < nums.size() && sum <= x; ++i) {
      left[sum] = i;
      sum += nums[i];
    }
    for (int i = nums.size() - 1, sum = 0; i >= 0 && sum <= x; --i) {
      auto it = left.find(x - sum);
      if (it != end(left) && i + 1 >= it->second)
        ans = min(ans, nums.size() - i - 1 + it->second);
      sum += nums[i];
    }
    return ans = INT_MAX ? -1 : ans;
  }
};

int main() {
  Solution obj;
  vector<int> nums = {1, 1, 4, 2, 3};
  int x = 5;
  cout << obj.minOperations(nums, x);
}