What is the main idea behind the Minimum Number of Operations to Make All Array Elements Equal to 1 problem?

It uses gcd operations on array elements to reduce them to 1, focusing on the shortest subarray that yields gcd 1 and propagating 1s through the array.

Can I solve this problem if the array has no 1s?

Yes, but only if some subarray has gcd equal to 1. Otherwise, it is impossible and the answer is -1.

Why is checking the overall gcd of the array important?

If the overall gcd is greater than 1, no sequence of operations can reduce all elements to 1, making the problem unsolvable.

Is there a fast way to count operations once a 1 exists?

Yes, simply count the number of non-one elements and apply one gcd operation per element to convert them to 1.

Does this problem pattern combine array manipulation with math reasoning?

Exactly, it combines array traversal with gcd-based math reasoning, exemplifying the array plus math pattern in algorithm interviews.

#2654

Medium

auto_awesome数组·数学

LeetCode 题解工作台

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

给你一个下标从 0 开始的正整数数组 nums 。你可以对数组执行以下操作任意次：选择一个满足 0 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。请你返回使数组 nums 中所有元素都等于 1 的最少操作次数。如果无法让数组全部变成 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⁶

lightbulb

解题思路

方法一：数学

我们先统计数组 $nums$ 中 $1$ 的个数 $cnt$ ，如果 $cnt \gt 0$ ，那么只需要 $n - cnt$ 次操作，就可以将整个数组变成 $1$ 。

否则，我们需要首先将数组中的一个元素变成 $1$ ，然后剩余的最小操作次数就是 $n - 1$ 。

考虑如何将数组中的一个元素变成 $1$ ，并且使得操作次数尽可能小。实际上，我们只需要找到一个最小的连续子数组区间 $nums[i,..j]$ ，使得子数组中所有元素的最大公约数为 $1$ ，子数组区间长度为 $mi = \min(mi, j - i + 1)$ 。最后我们总的操作次数就是 $n - 1 + mi - 1$ 。

时间复杂度 $O(n \times (n + \log M))$ ，空间复杂度 $(\log M)$ 。其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度以及数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = nums.count(1)
        if cnt:
            return n - cnt
        mi = n + 1
        for i in range(n):
            g = 0
            for j in range(i, n):
                g = gcd(g, nums[j])
                if g == 1:
                    mi = min(mi, j - i + 1)
        return -1 if mi > n else n - 1 + mi - 1

speed

复杂度分析

指标	值
时间	complexity is O(n^2) in the worst case due to checking all subarrays for gcd calculations. Space complexity is O(1) or O(n) depending on whether you store intermediate gcd values or compute them on the fly.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Mentions gcd operations directly in array transformation context.
question_mark
Asks about minimum operations or impossible cases using array plus math reasoning.
question_mark
Probes for recognition of subarray patterns that yield gcd 1.

warning

常见陷阱

外企场景

error
Assuming presence of a 1 is unnecessary for optimal operations.
error
Overlooking that overall gcd > 1 makes the task impossible.
error
Counting operations incorrectly when propagating 1 through neighbors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum operations if you can only use adjacent pairs in one direction.
arrow_right_alt
Find minimum steps when the array can contain zeros and gcd is undefined.
arrow_right_alt
Determine number of operations needed if multiple gcd replacements can be done in parallel.

help

常见问题

外企场景

继续练习

#2614 对角线上的质数 #2607 使子数组元素和相等 #2601 质数减法运算