---
# System prepended metadata

title: LC 1658. Minimum Operations to Reduce X to Zero
tags: [medium, leedcode, Sliding Window, c++]

---

# LC 1658. Minimum Operations to Reduce X to Zero

### [Problem link](https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

You are given an integer array <code>nums</code> and an integer <code>x</code>. In one operation, you can either remove the leftmost or the rightmost element from the array <code>nums</code> and subtract its value from <code>x</code>. Note that this  **modifies**  the array for future operations.

Return the  **minimum number**  of operations to reduce <code>x</code> to  **exactly**  <code>0</code> if it is possible, otherwise, return <code>-1</code>.

**Example 1:** 

```
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
```

**Example 2:** 

```
Input: nums = [5,6,7,8,9], x = 4
Output: -1
```

**Example 3:** 

```
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
```

 **Constraints:** 

- <code>1 <= nums.length <= 10<sup>5</sup></code>
- <code>1 <= nums[i] <= 10<sup>4</sup></code>
- <code>1 <= x <= 10<sup>9</sup></code>

## Solution 1 - Sliding Window
#### C++
```cpp=
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = accumulate(nums.begin(), nums.end(), 0) - x;
        if (sum < 0) {
            return -1;
        }
        int longest = -1;
        int cnt = 0;
        int l = 0;
        for (int r = 0; r < nums.size(); r++) {
            cnt += nums[r];
            while (cnt > sum) {
                cnt -= nums[l];
                l++;
            }
            if (cnt == sum) {
                longest = max(longest, r - l + 1);
            }
        }
        return longest == -1 ? -1 : nums.size() - longest;
    }
};
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(1)             |

## Note
Sol1: 逆向思維 + Sliding Window
[Ref.](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/solutions/2048811/ni-xiang-si-wei-pythonjavacgo-by-endless-b4jt/)
把問題轉換成「從 nums 中移除一個最長的子數組，使得剩餘元素的和為 x」。

換句話說，要從 nums 中找到最長的子數組，其元素和等於 s−x，這裡 s 為 nums 所有元素總和。
由於本題沒有負數，我們可以用滑動窗口, 最後答案為 nums 的長度減去最長子數組的長度。
