2654. Minimum Number of Operations to Make All Array Elements Equal to 1 Medium

1/**
2 * [2654] Minimum Number of Operations to Make All Array Elements Equal to 1
3 *
4 * You are given a 0-indexed array nums consisiting of positive integers. You can do the following operation on the array any number of times:
5 * 
6 * 	Select an index i such that 0 <= i < n - 1 and replace either of nums[i] or nums[i+1] with their gcd value.
7 * 
8 * Return the minimum number of operations to make all elements of nums equal to 1. If it is impossible, return -1.
9 * The gcd of two integers is the greatest common divisor of the two integers.
10 *  
11 * <strong class="example">Example 1:
12 * 
13 * Input: nums = [2,6,3,4]
14 * Output: 4
15 * Explanation: We can do the following operations:
16 * - Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].
17 * - Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].
18 * - Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].
19 * - Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].
20 * 
21 * <strong class="example">Example 2:
22 * 
23 * Input: nums = [2,10,6,14]
24 * Output: -1
25 * Explanation: It can be shown that it is impossible to make all the elements equal to 1.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	2 <= nums.length <= 50
31 * 	1 <= nums[i] <= 10^6
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/
37// discuss: https://leetcode.com/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn min_operations(nums: Vec<i32>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_2654() {
55    }
56}
57