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
Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.