题目（难度Medium）
给你一个下标从0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：
选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。
请你返回 使数组nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。
两个正整数的最大公约数指的是能整除这两个数的最大正整数。
示例 1
输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2
输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。
提示
2 <= nums.length <= 50
1 <= nums[i] <= 10^6
分析
首先，如果所有数的 GCD（最大公约数）大于 1，那么无论如何都无法操作出 1，我们返回−1。
如果 nums 中有一个 1，那么从 1 向左向右不断替换就能把所有数变成 1。
例如[2,2,1,2,2]→[2,1,1,2,2]→[1,1,1,2,2]→[1,1,1,1,2]→[1,1,1,1,1]，一共 n−1=5−1=4次操作。
如果有多个 1，那么每个 1 只需要向左修改，最后一个 1 向右修改剩余的数字。
例如 [2,1,2,1,2]→[1,1,2,1,2]→[1,1,1,1,2]→[1,1,1,1,1]，一共 n−cnt_1 = 5−2=3 次操作。
所以如果nums 中有 1，答案为
n−cnt_1
如果nums 中没有 1 呢？
想办法花费尽量少的操作得出一个1。
由于只能操作相邻的数，所以这个 1 必然是一个连续子数组的 GCD。
那么找到最短的 GCD 为 1 的子数组，设其长度为 minSize，那么我们需要操作 minSize−1 次得到1。
例如[2,6,3,4] 中的 [3,4]可以操作 2−1=1 次得到1。
然后就转化成提示 1 中的情况了，最终答案为
(minSize−1)+(n−1)=minSize + n − 2
复杂度分析
时间复杂度：O(n(n+logU))，其中n 为 nums 的长度，内层循环的时间复杂度为 O(n+logU)，所以总的时间复杂度为O(n(n+logU))。
空间复杂度：O(1)。仅用到若干额外变量。
代码
class Solution {public:int minOperations(vector<int> &nums) {int n = nums.size(), gcd_all = 0, cnt1 = 0;for (int x: nums) {// 所有数的最大公约数gcd_all = gcd(gcd_all, x);// 记录1的个数cnt1 += x == 1;}// 所有数的最大公约数不是1，不能将所有元素变成1if (gcd_all > 1) return -1;if (cnt1) return n - cnt1;// 最短GCD为1的数组的大小int min_size = n;for (int i = 0; i < n; ++i) {int g = 0;for (int j = i; j < n; ++j) {g = gcd(g, nums[j]);if (g == 1) {min_size = min(min_size, j - i + 1);break;}}}return min_size + n - 2;}};
题目链接
https://leetcode.cn/contest/weekly-contest-342/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/
参考链接
https://leetcode.cn/circle/discuss/gV9fIg/view/wd7eFL/
