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

题目

6392. 使数组所有元素变成 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] <= 10^6

题解

方法一：

思路

这是一个思维题。

当出现1的时候，相邻非1的数可以和1求最大公约数然后变为1. 所以出现1的时候，非1的个数就是需要操作的最少次数。

当没有出现1的时候，这个时候我们需要通过求一段区间的gcd为1。这段区间的长度-1就是操作的次数。当出现1的时候就转化为上一种情况。
所以区间gcd为1的最短的区间长度+n-2就是需要操作的最少次数。

本题数组长度最多n=50，所以可以用$O(n^2logn)$通过。

直接双重for循环枚举所有区间即可。然后在枚举时可以求出其中gcd=1的最短区间长度。

代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int o = count(nums.begin(), nums.end(), 1);
        if (o) {
            return n-o;
        }
        int c = 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) {
                    c = min(c, j-i);
                    break;
                }
            }
        }
        // cout << c << endl;
        if (c == n) return -1;
        return c+n-1;
    }
};

方法二：

思路

我们还可以优化时间复杂度，理论上可以优化到O(nlogn)

我们观察一下区间gcd的性质。

当区间长度增加时，gcd不会减小。所以如果我们固定区间右端点r，随着区间左端点l增大，区间[l,r]的gcd是非递减的。

我们试想一个区间的gcd不为1最多能有多少个不同的值在这个区间内？如果区间内的数由大到小排列成$[a_1, a_2, a_3,\cdots, a_n]$，$a_1$必须是其他数的倍数，$a_2$必须是$a_i,i>2$的倍数。。。我们发现能让区间最长且gcd不为1的情况是这样的$[2,4,8,16,\cdots,2^n]$。因此区间内不同的gcd值就不超过log(n)个。

通过以上两个性质，发现在确定右端点r的情况下，左端点l增长区间[l,r]的gcd不会减少，且存在大量重复，不同的个数就log(n)个。

我们可以去除重复，且对于相同的gcd只记录下标最大的一个。

定义f[r][g]为以r为右端点的区间中区间gcd为g的最大下标l。这样以r为右端点的gcd为g的最小区间就是[l,r]。

由于我们要求gcd为1的最小区间长度。因此对于每个r，求出最小的r-f[r][1]+1即可。

那么以r+1为右端点怎么求呢？
从小到大枚举f[r]中的g，g的个数是对数数量级的，并不会超时。f[r][g]随g增大而增大。所以有转移式 f[r+1][gcd(g,nums[r+1])] = f[r][g]

f[r+1]转移只与f[r]有关因此可以用滚动集合。减少空间复杂度。

代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int o = count(nums.begin(), nums.end(), 1);
        if (o) return n-o;
        map<int,int> mp; // mp[i] gcd 为i的最右侧下标
        int min_len = n+5; // inf
        for (int i=0; i<n; i++) {
            map<int,int> t;
            for (auto [k,v]:mp) {
                t[gcd(k, nums[i])] = v;
            }
            t[nums[i]] = i;
            mp = t;
            if (mp.begin()->first  == 1) {
                min_len = min(min_len, i-mp.begin()->second+1);
            }
        }
        if (min_len == n+5) return -1;
        return min_len+n-2;
    }
};