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
28
29
30
31
32
33
34
35
36
37
38
|
use std::cmp::min;
struct Solution;
impl Solution {
pub fn min_operations(nums: Vec<i32>, x: i32) -> i32 {
Self::min_operations_slice(&nums[..], x).unwrap_or(-1)
}
pub fn min_operations_slice(nums: &[i32], x: i32) -> Option<i32> {
if x < 0 || nums.is_empty() {return None;}
if x == 0 {return Some(0);}
match (
Self::min_operations_slice(&nums[..nums.len() - 1], x - &nums[nums.len() - 1]),
Self::min_operations_slice(&nums[1..], x - &nums[0])
) {
(None, None) => None,
(Some(x), Some(y)) => Some(min(x,y)+1),
(Some(x),None) | (None, Some(x)) => Some(x+1)
}
}
}
fn main() {
let tests = vec![
(vec![1,1,4,2,3], 5, 2),
(vec![5,6,7,8,9], 4, -1),
(vec![3,2,20,1,1,3], 10, 5),
(vec![1,1], 3, -1),
(vec![1241,8769,9151,3211,2314,8007,3713,5835,2176,8227,5251,9229,904,1899,5513,7878,8663,3804,2685,3501,1204,9742,2578,8849,1120,4687,5902,9929,6769,8171,5150,1343,9619,3973,3273,6427,47,8701,2741,7402,1412,2223,8152,805,6726,9128,2794,7137,6725,4279,7200,5582,9583,7443,6573,7221,1423,4859,2608,3772,7437,2581,975,3893,9172,3,3113,2978,9300,6029,4958,229,4630,653,1421,5512,5392,7287,8643,4495,2640,8047,7268,3878,6010,8070,7560,8931,76,6502,5952,4871,5986,4935,3015,8263,7497,8153,384,1136], 894887480, 0)
];
for (nums, x, out) in tests {
let result = Solution::min_operations(nums.clone(), x);
println!("{nums:?} {x} is {result} should be {out}");
}
}
|
