3605. Minimum Stability Factor of Array Hard

1/**
2 * [3605] Minimum Stability Factor of Array
3 *
4 * You are given an integer array nums and an integer maxC.
5 * A <span data-keyword="subarray">subarray</span> is called stable if the highest common factor (HCF) of all its elements is greater than or equal to 2.
6 * The stability factor of an array is defined as the length of its longest stable subarray.
7 * You may modify at most maxC elements of the array to any integer.
8 * Return the minimum possible stability factor of the array after at most maxC modifications. If no stable subarray remains, return 0.
9 * Note:
10 * 
11 * 	The highest common factor (HCF) of an array is the largest integer that evenly divides all the array elements.
12 * 	A subarray of length 1 is stable if its only element is greater than or equal to 2, since HCF([x]) = x.
13 * 
14 * <div class="notranslate" style="all: initial;"> </div>
15 *  
16 * <strong class="example">Example 1:
17 * <div class="example-block">
18 * Input: <span class="example-io">nums = [3,5,10], maxC = 1</span>
19 * Output: <span class="example-io">1</span>
20 * Explanation:
21 * 
22 * 	The stable subarray [5, 10] has HCF = 5, which has a stability factor of 2.
23 * 	Since maxC = 1, one optimal strategy is to change nums[1] to 7, resulting in nums = [3, 7, 10].
24 * 	Now, no subarray of length greater than 1 has HCF >= 2. Thus, the minimum possible stability factor is 1.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">nums = [2,6,8], maxC = 2</span>
29 * Output: <span class="example-io">1</span>
30 * Explanation:
31 * 
32 * 	The subarray [2, 6, 8] has HCF = 2, which has a stability factor of 3.
33 * 	Since maxC = 2, one optimal strategy is to change nums[1] to 3 and nums[2] to 5, resulting in nums = [2, 3, 5].
34 * 	Now, no subarray of length greater than 1 has HCF >= 2. Thus, the minimum possible stability factor is 1.
35 * </div>
36 * <strong class="example">Example 3:
37 * <div class="example-block">
38 * Input: <span class="example-io">nums = [2,4,9,6], maxC = 1</span>
39 * Output: <span class="example-io">2</span>
40 * Explanation:
41 * 
42 * 	The stable subarrays are:
43 * 	
44 * 		[2, 4] with HCF = 2 and stability factor of 2.
45 * 		[9, 6] with HCF = 3 and stability factor of 2.
46 * 	
47 * 	
48 * 	Since maxC = 1, the stability factor of 2 cannot be reduced due to two separate stable subarrays. Thus, the minimum possible stability factor is 2.
49 * </div>
50 *  
51 * Constraints:
52 * 
53 * 	1 <= n == nums.length <= 10^5
54 * 	1 <= nums[i] <= 10^9
55 * 	0 <= maxC <= n
56 * 
57 */
58pub struct Solution {}
59
60// problem: https://leetcode.com/problems/minimum-stability-factor-of-array/
61// discuss: https://leetcode.com/problems/minimum-stability-factor-of-array/discuss/?currentPage=1&orderBy=most_votes&query=
62
63// submission codes start here
64
65impl Solution {
66    pub fn min_stable(nums: Vec<i32>, max_c: i32) -> i32 {
67        0
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_3605() {
79    }
80}
81