首页算法

2654. 使数组所有元素变成 1 的最少操作次数

难度中等

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

# 暴力枚举

若没有 1

  • 暴力枚举连续子数组，选择 gcd 后含有 1 的最短子数组

  • 为什么需要连续？

    假设是不连续的子数组，此时已经出现 1 了，那么其余不连续的已经是多余的

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for (int num : nums) {
            if (num == 1) {
                cnt++;
            }
        }
        if (cnt > 0) {
            // 其余的需要 n - cnt 次
            return n - cnt;
        }
        int ans = n;
        // 枚举以 i 开始的连续子数组
        for (int i = 0; i < n; i++) {
            int g = nums[i];
            for (int j = i + 1; j < n; j++) {
                g = gcd(g, nums[j]);
                if (g == 1) {
                    ans = Math.min(ans, j - i);
                }
            }
        }
        return ans == n ? -1 : n - 1 + ans;
    }
    
    public int gcd(int a, int b) {
        while (b > 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
}

# 利用 gcd 的性质

若没有 1

  • 暴力枚举连续子数组，选择 gcd 后含有 1 的最短子数组

  • 为什么需要连续？

    假设是不连续的子数组，此时已经出现 1 了，那么其余不连续的已经是多余的

由上述可以看出每次需要循环一遍重复求出 gcd

例如：[2, 6, 3, 4]

  • g: [2]

    g: [2, 6]

    g: [1, 3, 3]

    g: [1, 1, 1, 4]

利用上一次求出的 gcd 从而求出当前的 gcd

不同的 gcd 个数最多 log(n)log(n) 个

  • 要么减半，要么为 1

只需要对 gcd 数组【去重】，并且保存重复 gcd 的【最大下标】

gcd 数组从右往左肯定是倍数下降的，最后只需判断第一个元素是不是 1 即可

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for (int num : nums) {
            if (num == 1) {
                cnt++;
            }
        }
        if (cnt > 0) {
            // 其余的需要 n - 1 次
            return n - cnt;
        }
        int ans = n;
        // 以 i 结尾的 gcd 数组
        List<int[]> gs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<int[]> ts = new ArrayList<>();
            for (int[] g : gs) {
                ts.add(new int[]{gcd(g[0], nums[i]), g[1]});
            }
            ts.add(new int[]{nums[i], i});
            gs = ts;
            // 对 gs 去重
            int l = 0;
            for (int j = 1; j < gs.size(); j++) {
                int[] gr = gs.get(j);
                int[] gl = gs.get(l);
                if (gr[0] != gl[0]) {
                    l++;
                }
                if (gl[0] == gr[0]) {
                    gs.set(l, new int[]{gl[0], Math.max(gl[1], gr[1])});   
                } else {
                    gs.set(l, gr);
                }
            }
            gs = gs.subList(0, l + 1);
            int[] g = gs.get(0);
            // 选择小的区间
            if (g[0] == 1) {
                ans = Math.min(i - g[1], ans);
            }
        }
        return ans == n ? -1 : n - 1 + ans;
    }
    
    public int gcd(int a, int b) {
        while (b > 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
}

# 复杂度分析

  • 时间复杂度 ：O(nlogU)O(nlogU)，gcdgcd 减半的次数为 logUlogU

  • 空间复杂度 ：O(logU)O(logU)

相似题目：利用 gcd 的性质 最大公因数等于 K 的子数组数目