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

难度: 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⁶

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        if gcd(*nums) > 1:
            return -1
        n = len(nums)
        cnt1 = sum(x == 1 for x in nums)
        if cnt1:
            return n - cnt1

        min_size = n
        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中
                    min_size = min(min_size, j - i)
                    break
        return min_size + n - 1

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/solutions/2241277/liang-chong-fang-fa-bao-li-mei-ju-li-yon-refp/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

该题解通过两个主要步骤来解决问题：首先，检查数组中所有元素的最大公约数（GCD）。如果全局GCD大于1，则无法将所有元素变为1，因此返回-1。其次，如果数组中已经有值为1的元素，则直接通过这些1来尽快将其他元素转换成1，操作次数为数组长度减去已有1的数量。如果数组中无1，则使用暴力方法，枚举所有可能的子数组，并计算子数组的累计GCD，找到最短的能够通过GCD操作得到1的子数组长度，并通过这个最短长度加上n-1来计算总的操作次数。

时间复杂度: O(n^3 log M)

空间复杂度: O(1)

# 定义解决方案类
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # 检查数组元素的全局GCD
        if gcd(*nums) > 1:
            return -1  # 如果全局GCD大于1，无法全部变为1，返回-1
        n = len(nums)  # 数组长度
        cnt1 = sum(x == 1 for x in nums)  # 计算数组中1的数量
        if cnt1:
            return n - cnt1  # 如果已有1，则返回需要的操作次数

        min_size = n  # 初始化最小长度为n
        for i in range(n):
            g = 0  # 初始化GCD为0
            for j in range(i, n):
                g = gcd(g, nums[j])  # 更新GCD
                if g == 1:
                    # 如果当前GCD为1
                    min_size = min(min_size, j - i)  # 更新最短长度
                    break
        return min_size + n - 1  # 返回总操作次数

Explore

首先检查数组中所有元素的全局GCD是为了判断是否有可能通过任何操作将所有元素转换为1。如果全局GCD大于1，意味着数组中所有元素都至少可以被一个大于1的数整除，因此不可能通过任何数学操作（如除法或减法）仅将数组中的每个元素转换为1。这一步骤是算法的关键优化，它可以快速判断并结束程序，避免不必要的计算。

`gcd(*nums)`这一行代码用于计算数组`nums`中所有元素的最大公约数。此处的星号操作符（*）是Python的参数解包操作符，它将列表或元组`nums`中的所有元素作为独立的参数传递给`gcd`函数。这是因为`gcd`函数在Python标准库中通常只接受两个参数，使用星号可以让它接受任意数量的参数，从而一次计算整个数组的GCD。

如果全局GCD大于1，即数组中所有元素的最大公约数是一个大于1的整数，这意味着数组中的每个元素都可以被这个公约数整除。因此，没有办法通过除以这个公约数或其他任何数使得所有元素变为1，因为除以这个公约数后，每个元素仍然会是一个大于1的整数。此外，任何基于GCD的操作都不能将数值减小到1以外的任何数字，除非起始GCD本身为1。

这种计算逻辑基于将找到的最短子数组（其GCD为1）使用为基准，通过逐步扩展这个基准来影响整个数组的考虑。计算中的`min_size + n - 1`反映了两部分操作：首先，`min_size`是使得子数组的GCD为1的最小步骤数；其次，`n - 1`代表至少需要进行的操作次数，将这个最小的GCD为1的子数组的效果扩散到整个数组，即每次操作向未处理的部分扩散一个元素的距离。这样的步骤确保了整个数组的每个元素最终都能被转化为1。