1658. Minimum Operations to Reduce X to Zero

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

Return the minimum number of operations to reduce `x` to exactly `0` if it's possible, otherwise, return `-1`.

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:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 104`
• `1 <= x <= 109`

1658. Minimum Operations to Reduce X to Zero
``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
let n = nums.len();
let sum: i32 = nums.iter().sum();
let y = sum - x;
if y == 0 {
return n as i32;
}
let mut hm: HashMap<i32, usize> = HashMap::new();
let mut prev = 0;
hm.insert(0, 0);
let mut max = 0;
for i in 0..n {
prev += nums[i];
hm.insert(prev, i + 1);
if let Some(j) = hm.get(&(prev - y)) {
max = max.max(i + 1 - j);
}
}

if max == 0 {
-1
} else {
(n - max) as i32
}
}
}

#[test]
fn test() {
let nums = vec![1, 1, 4, 2, 3];
let x = 5;
let res = 2;
assert_eq!(Solution::min_operations(nums, x), res);
let nums = vec![5, 6, 7, 8, 9];
let x = 4;
let res = -1;
assert_eq!(Solution::min_operations(nums, x), res);
let nums = vec![3, 2, 20, 1, 1, 3];
let x = 10;
let res = 5;
assert_eq!(Solution::min_operations(nums, x), res);
let nums = vec![
8828, 9581, 49, 9818, 9974, 9869, 9991, 10000, 10000, 10000, 9999, 9993, 9904, 8819, 1231,
6309,
];
let x = 134365;
let res = 16;
assert_eq!(Solution::min_operations(nums, x), res);
}
``````