2366. Minimum Replacements to Sort the Array Hard

1/**
2 * [2366] Minimum Replacements to Sort the Array
3 *
4 * You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.
5 * 
6 * 	For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].
7 * 
8 * Return the minimum number of operations to make an array that is sorted in non-decreasing order.
9 *  
10 * Example 1:
11 * 
12 * Input: nums = [3,9,3]
13 * Output: 2
14 * Explanation: Here are the steps to sort the array in non-decreasing order:
15 * - From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
16 * - From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
17 * There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.
18 * 
19 * Example 2:
20 * 
21 * Input: nums = [1,2,3,4,5]
22 * Output: 0
23 * Explanation: The array is already in non-decreasing order. Therefore, we return 0. 
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	1 <= nums.length <= 10^5
29 * 	1 <= nums[i] <= 10^9
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/
35// discuss: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
41        
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_2366() {
53    }
54}
55