题目

给你一个下标从 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 就像一个“催化剂”或“病毒”，因为它具有以下特性： gcd(x, 1) = 1 (对于任何正整数 x)

这意味着：

一旦数组中存在一个 1，我们就可以用它把它的邻居“感染”成 1。
这个新生成的 1 又可以继续“感染”它的邻居。
这个“感染”过程是最高效的，每次操作固定能产生一个 1。

基于洞察的分类讨论

根据数组中是否已经存在 1，我们可以把问题分为两种截然不同的情况：

情况一：数组中已经有 `1` (最佳情况)

这是最简单的情况。假设数组长度为 n，且里面已经有 one_count 个 1 ( one_count >= 1 )。

策略： 我们不需要再“创造” 1 了。我们只需要利用已有的 1，通过 gcd(x, 1) = 1 的操作，把所有非 1 的元素全部“感染”掉。
示例： nums = [2, 6, 1, 4]
1. 用 nums[2] 的 1 感染 nums[1]：[2, gcd(6, 1), 1, 4] -> [2, 1, 1, 4] (1 次操作)
2. 用 nums[1] 的 1 感染 nums[0]：[gcd(2, 1), 1, 1, 4] -> [1, 1, 1, 4] (1 次操作)
3. 用 nums[2] 的 1 感染 nums[3]：[1, 1, 1, gcd(1, 4)] -> [1, 1, 1, 1] (1 次操作)
结论： 数组中有 n - one_count 个非 1 的元素，我们只需要 n - one_count 次“感染”操作就可以把它们全部变成 1。
答案： n - one_count

情况二：数组中没有 `1` (常规或最差情况)

如果数组中一个 1 都没有，我们的任务就分成了两个阶段：

阶段 A：必须先“创造”出第一个 1

我们必须通过 gcd 操作，从 0 开始造出第一个 1。
gcd 操作只能在相邻元素间进行。要得到 1，我们必须找到一个连续的子数组 nums[i...j]，使得这个子数组中所有元素的 gcd 等于 1。
例如，对于 [a, b, c]，如果 gcd(a, b, c) = 1，我们可以：
1. [a, gcd(b, c), c] -> [a, b', c]
2. [gcd(a, b'), b', c] -> [1, b', c]
操作次数： 将一个长度为 k 的子数组 [nums[i], ..., nums[j]] (其中 k = j - i + 1) 压缩成一个 1，需要 k - 1 次操作。
优化： 为了使“阶段 A”的操作数最少，我们必须在数组中找到 gcd 为 1 的最短的那个连续子数组。设这个最短长度为 min_len。
阶段 A 的成本： min_len - 1 次操作。

阶段 B：传播这个新创造出来的 1

一旦我们花了 min_len - 1 步造出了第一个 1，数组中就有 1 个 1 和 n - 1 个其他元素。
此时，我们回到了情况一。
我们需要额外的 n - 1 次操作来把这个 1 传播到整个数组。
阶段 B 的成本： n - 1 次操作。
结论： 总操作数 = (阶段 A 成本) + (阶段 B 成本) = (min_len - 1) + (n - 1)
答案： min_len + n - 2

情况三：无法创造 `1` (最差情况的特例)

这是“情况二”的一种特例。如果在“阶段 A”中，我们搜索了所有可能的连续子数组，都找不到任何一个 gcd 为 1 的子数组。

发生条件： 这意味着数组所有元素的 gcd 本身就大于 1（例如 [2, 4, 6, 10]，它们的 gcd 是 2）。
结论： 无论怎么操作，gcd(a, b) 的结果永远是 gcd(a,b) 的倍数，它永远不可能变成 1。
答案： -1

最终算法流程

检查 1： 遍历数组，统计 1 的个数 one_count。
判断情况一： 如果 one_count > 0，直接返回 n - one_count。
进入情况二/三： 如果 one_count == 0，我们必须去寻找 min_len。
- 初始化 min_len = 无穷大 (或一个大于 n 的数)。
- 使用双重循环遍历所有可能的连续子数组 nums[i...j]：
  - 外层循环 i 从 0 到 n-1。
  - 内层循环 j 从 i 到 n-1。
  - 计算 g = gcd(nums[i], ..., nums[j])。（优化：可以在内层循环中迭代计算 g = gcd(g, nums[j])）
  - 如果 g == 1：
    - 我们找到了一个 gcd 为 1 的子数组，其长度为 k = j - i + 1。
    - 更新 min_len = min(min_len, k)。
    - （优化：一旦 g==1，内层 j 的循环就可以 break 了，因为我们只关心从 i 出发的最短长度）。
返回结果：
- 如果 min_len 仍然是 无穷大 (说明没找到 g==1 的子数组)，返回 -1 (情况三)。
- 否则，返回 min_len + n - 2 (情况二)。

具体代码

func minOperations(nums []int) int {

    left := 0
    right := 0
    n := len(nums)
    min_gcd_list := n
    one_count := 0

    for _, num := range nums {
        if num == 1 {
            one_count++
        }
    }

    if one_count >= 1 {
        return n - one_count
    }

    for right < n {

        cur_list := nums[left:right + 1]
        if gcdMany(cur_list) != 1 {
            right++
        } else {
            min_gcd_list = min(min_gcd_list, len(cur_list))
            if len(cur_list) == 1 {
                right++
            }
            left++
        }
    }

    if left != 0 {
        return min_gcd_list + n - 2
    } else {
        return -1
    }

}

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func gcdMany(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	result := nums[0]
	for _, n := range nums[1:] {
		result = gcd(result, n)
	}
	return result
}

复杂度

时间复杂度： $O(N^2 \cdot \log M)$
空间复杂度： $O(1)$

1. 辅助函数 `gcd(a, b)`

功能： 计算两个数的最大公约数。
时间复杂度： $O(\log M)$
- 使用的是欧几里得算法（辗转相除法）。
- 该算法的步数（模运算的次数）在最坏情况下与输入数字的对数成正比。
- 设 $M$ 是 nums 中元素的最大值（$10^6$），那么单次 gcd 操作的时间复杂度上界为 $O(\log(\min(a, b)))$，我们可以统一记为 $O(\log M)$。
空间复杂度： $O(1)$
- 该函数只使用了固定数量的变量（a, b），是常数空间。

2. 辅助函数 `gcdMany(nums []int)`

功能： 计算一个切片中所有元素的 gcd。
时间复杂度： $O(k \cdot \log M)$
- 设传入的切片 nums 的长度为 $k$。
- if len(nums) == 0: $O(1)$
- result := nums[0]: $O(1)$
- for _, n := range nums[1:]: 这个循环执行 $k-1$ 次。
- result = gcd(result, n): 循环体内部调用 gcd 函数。
- 每次 gcd 调用耗时 $O(\log M)$。
- 总时间 = (循环次数) $\times$ (循环体时间) = $(k-1) \times O(\log M) = O(k \cdot \log M)$。
空间复杂度： $O(1)$
- 该函数只使用了固定数量的变量（result, n），是常数空间。传入的 nums 是一个切片，在 Go 中是引用传递（传递的是切片头信息），不会复制底层数组。

3. 主函数 `minOperations(nums []int)`

我们将 $N$ 定义为 len(nums)。

空间复杂度： $O(1)$

left, right, n, min_gcd_list, one_count：这些都是 $O(1)$ 的基本类型变量。
for _, num := range nums: 循环变量 num 占用 $O(1)$。
cur_list := nums[left:right + 1]: 这是关键。在 Go 中，对一个切片进行切片操作（slicing）并_不会_复制底层的数组数据。它只是创建了一个新的“切片头”（一个包含指针、长度和容量的小结构体）。这个操作本身是 $O(1)$ 时间和 $O(1)$ 空间。
调用 gcdMany(cur_list)：我们已经分析过，gcdMany 自身只使用 $O(1)$ 的_额外_空间。

结论： 整个函数只使用了固定数量的变量和切片头，其空间占用与输入大小 $N$ 无关。因此，空间复杂度为 $O(1)$。

时间复杂度： $O(N^2 \cdot \log M)$

one_count 循环：
- for _, num := range nums { ... }
- 这个循环遍历 nums 一次，执行 $N$ 次 $O(1)$ 操作。
- 时间： $O(N)$
最佳情况（one_count >= 1）：
- 如果数组中已经有 1，代码会立即 return n - one_count。
- 这种情况下，总时间就是 $O(N)$（来自 one_count 循环）。
最坏情况（one_count == 0）：
- 此时代码进入 for right < n 循环。我们必须分析这个循环。
- 循环结构：这是一个 while 循环。在循环体内部，if-else 语句确保了每次迭代，left 和 right 两个指针中有且仅有一个会加一（right++ 或 left++）。
- 迭代次数： right 指针从 0 开始，最多增加到 $N$（导致循环终止）。left 指针从 0 开始，最多增加到 $N$。因此，left 和 right 指针的总移动次数是 $O(N + N) = O(N)$。这意味着 for 循环体最多执行 $O(N)$ 次。
- 循环体内的成本： 这是分析的陷阱。虽然循环迭代 $O(N)$ 次，但我们必须看单次迭代的成本。
  - cur_list := nums[left:right + 1]: $O(1)$ 时间。
  - gcdMany(cur_list): 这是主要成本。
- 分析 gcdMany 的成本：
  - gcdMany 的成本是 $O(k \cdot \log M)$，其中 $k$ 是 cur_list 的长度。
  - k = right - left + 1。
  - 在循环过程中，$k$ 的值会变化。
- 计算总时间（最坏情况）：
  - 考虑一个输入，gcd 永远不等于 1（例如 [2, 4, 6, 8, ...]）。
  - left 将永远保持为 0。
  - if gcdMany(...) != 1 永远为 true。
  - 循环将像这样执行：
    - l=0, r=0: 迭代 1。调用 gcdMany(len=1)。成本 $O(1 \cdot \log M)$。right++。
    - l=0, r=1: 迭代 2。调用 gcdMany(len=2)。成本 $O(2 \cdot \log M)$。right++。
    - l=0, r=2: 迭代 3。调用 gcdMany(len=3)。成本 $O(3 \cdot \log M)$。right++。
    - ...
    - l=0, r=N-1: 迭代 $N$。调用 gcdMany(len=N)。成本 $O(N \cdot \log M)$。right++。
    - r 变为 $N$，循环终止。
- 总时间（循环）：
  - 总时间是所有迭代成本的总和。
  - $Total = O(1 \cdot \log M) + O(2 \cdot \log M) + ... + O(N \cdot \log M)$
  - $Total = O(\log M) \cdot (1 + 2 + 3 + ... + N)$
  - 我们知道 $1 + 2 + ... + N = \frac{N(N+1)}{2}$，
  - 所以总和是 $O(N^2)$。
  - 循环总时间： $O(N^2 \cdot \log M)$
综合结论（时间）：
- one_count 循环：$O(N)$
- for right < n 循环：$O(N^2 \cdot \log M)$
- 总时间 = $O(N) + O(N^2 \cdot \log M)$
- 取主导项，最终时间复杂度为 $O(N^2 \cdot \log M)$。

另一个更好理解的双重循环

func minOperations(nums []int) int {
    n := len(nums)
    one_count := 0
    for _, num := range nums {
        if num == 1 {
            one_count++
        }
    }

    // --- 情况 1：数组中已经有 1 ---
    // 这是最高效的情况，直接 "感染" 即可
    if one_count >= 1 {
        return n - one_count
    }

    // --- 情况 2 & 3：数组中没有 1 ---
    // 我们必须先 "创造" 一个 1
    // min_len 用来记录 gcd(nums[i...j]) == 1 的最短子数组长度
    min_len := math.MaxInt32 // 初始化为 "无穷大"

    // O(N^2) 双重循环查找最短子数组
    for i := 0; i < n; i++ {
        // current_gcd 存储 nums[i...j] 的最大公约数
        current_gcd := nums[i]
        
        // 注意：j 从 i 开始
        for j := i; j < n; j++ {
            // 动态更新 current_gcd
            current_gcd = gcd(current_gcd, nums[j])
            
            // 找到了！
            if current_gcd == 1 {
                // 记录子数组的长度
                min_len = min(min_len, j - i + 1)
                
                // 优化：我们只需要从 i 开始的 "最短" 那个
                // 没必要继续向右（j++）了，直接 break 内层循环
                break
            }
        }
    }

    // --- 情况 3：无法创造 1 ---
    // 如果 min_len 还是 "无穷大"，说明没找到任何 gcd 为 1 的子数组
    if min_len == math.MaxInt32 {
        return -1
    }

    // --- 情况 2：可以创造 1 ---
    // (min_len - 1) 步是 "创造" 第一个 1 所需的操作
    // (n - 1) 步是 "传播" 这个 1 到全数组所需的操作
    return (min_len - 1) + (n - 1)
}

// gcd 函数 (你的版本，无需改动)
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

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

beautifulremi

题目

解题思路

基于洞察的分类讨论

情况一：数组中已经有 `1` (最佳情况)

情况二：数组中没有 `1` (常规或最差情况)

情况三：无法创造 `1` (最差情况的特例)

最终算法流程

具体代码

复杂度

1. 辅助函数 `gcd(a, b)`

2. 辅助函数 `gcdMany(nums []int)`

3. 主函数 `minOperations(nums []int)`

空间复杂度： $O(1)$

时间复杂度： $O(N^2 \cdot \log M)$

另一个更好理解的双重循环

题目

解题思路

基于洞察的分类讨论

情况一：数组中已经有 1 (最佳情况)

情况二：数组中没有 1 (常规或最差情况)

情况三：无法创造 1 (最差情况的特例)

最终算法流程

具体代码

复杂度

1. 辅助函数 gcd(a, b)

2. 辅助函数 gcdMany(nums []int)

3. 主函数 minOperations(nums []int)

空间复杂度： $O(1)$

时间复杂度： $O(N^2 \cdot \log M)$

另一个更好理解的双重循环

情况一：数组中已经有 `1` (最佳情况)

情况二：数组中没有 `1` (常规或最差情况)

情况三：无法创造 `1` (最差情况的特例)

1. 辅助函数 `gcd(a, b)`

2. 辅助函数 `gcdMany(nums []int)`

3. 主函数 `minOperations(nums []int)`