2835. Minimum Operations to Form Subsequence With Target Sum Hard

1/**
2 * [2835] Minimum Operations to Form Subsequence With Target Sum
3 *
4 * You are given a 0-indexed array nums consisting of non-negative powers of 2, and an integer target.
5 * In one operation, you must apply the following changes to the array:
6 * 
7 * 	Choose any element of the array nums[i] such that nums[i] > 1.
8 * 	Remove nums[i] from the array.
9 * 	Add two occurrences of nums[i] / 2 to the end of nums.
10 * 
11 * Return the minimum number of operations you need to perform so that nums contains a subsequence whose elements sum to target. If it is impossible to obtain such a subsequence, return -1.
12 * A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
13 *  
14 * <strong class="example">Example 1:
15 * 
16 * Input: nums = [1,2,8], target = 7
17 * Output: 1
18 * Explanation: In the first operation, we choose element nums[2]. The array becomes equal to nums = [1,2,4,4].
19 * At this stage, nums contains the subsequence [1,2,4] which sums up to 7.
20 * It can be shown that there is no shorter sequence of operations that results in a subsequnce that sums up to 7.
21 * 
22 * <strong class="example">Example 2:
23 * 
24 * Input: nums = [1,32,1,2], target = 12
25 * Output: 2
26 * Explanation: In the first operation, we choose element nums[1]. The array becomes equal to nums = [1,1,2,16,16].
27 * In the second operation, we choose element nums[3]. The array becomes equal to nums = [1,1,2,16,8,8]
28 * At this stage, nums contains the subsequence [1,1,2,8] which sums up to 12.
29 * It can be shown that there is no shorter sequence of operations that results in a subsequence that sums up to 12.
30 * <strong class="example">Example 3:
31 * 
32 * Input: nums = [1,32,1], target = 35
33 * Output: -1
34 * Explanation: It can be shown that no sequence of operations results in a subsequence that sums up to 35.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	1 <= nums.length <= 1000
40 * 	1 <= nums[i] <= 2^30
41 * 	nums consists only of non-negative powers of two.
42 * 	1 <= target < 2^31
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/minimum-operations-to-form-subsequence-with-target-sum/
48// discuss: https://leetcode.com/problems/minimum-operations-to-form-subsequence-with-target-sum/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn min_operations(nums: Vec<i32>, target: i32) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_2835() {
66    }
67}
68