日期: 2025 年 11 月 12 日

目标

给你一个下标从 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

思路

有一个正整数数组 nums，每次操作可以将 nums[i] 或者 nums[i + 1] 替换成它们的最大公约数。求将 nums 所有元素变为 1 的最小操作次数，如果无法完成，返回 -1。

显然只要存在相邻的互质元素，就可以将其中的一个设置为 1，然后就可以将左右的元素按顺序替换为 1，总共需要操作 n 次。目标是如何用最小的操作次数使得存在一对相邻元素互质。暴力枚举 子数组 的起点与终点，计算所有元素的最大公约数，记录最小的子数组长度。

代码

/**
 * @date 2025-11-12 9:07
 */
public class MinOperations2654 {

    public int minOperations(int[] nums) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        int oneCnt = 0;
        int gcdAll = nums[0];
        for (int num : nums) {
            if (num == 1) {
                oneCnt++;
            }
            gcdAll = gcd(gcdAll, num);
        }
        if (gcdAll > 1) {
            return -1;
        }
        if (oneCnt > 0) {
            return n - oneCnt;
        }
        for (int i = 0; i < n; i++) {
            int g = nums[i];
            for (int j = i; j < n; j++) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    res = Math.min(res, j - i + 1);
                    break;
                }
            }
        }
        return res - 2 + n;
    }

    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}

性能