题目描述
给你一个下标从 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 <= 501 <= nums[i] <= 106
解法
方法一：数学
我们先统计数组 $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 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int cnt = 0;
for (int x : nums) {
if (x == 1) {
++cnt;
}
}
if (cnt > 0) {
return n - cnt;
}
int mi = n + 1;
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) {
mi = Math.min(mi, j - i + 1);
}
}
}
return mi > n ? -1 : n - 1 + mi - 1;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
int cnt = 0;
for (int x : nums) {
if (x == 1) {
++cnt;
}
}
if (cnt) {
return n - cnt;
}
int mi = n + 1;
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) {
mi = min(mi, j - i + 1);
}
}
}
return mi > n ? -1 : n - 1 + mi - 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | func minOperations(nums []int) int {
n := len(nums)
cnt := 0
for _, x := range nums {
if x == 1 {
cnt++
}
}
if cnt > 0 {
return n - cnt
}
mi := n + 1
for i := 0; i < n; i++ {
g := 0
for j := i; j < n; j++ {
g = gcd(g, nums[j])
if g == 1 {
mi = min(mi, j-i+1)
}
}
}
if mi > n {
return -1
}
return n - 1 + mi - 1
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | function minOperations(nums: number[]): number {
const n = nums.length;
let cnt = 0;
for (const x of nums) {
if (x === 1) {
++cnt;
}
}
if (cnt > 0) {
return n - cnt;
}
let mi = n + 1;
for (let i = 0; i < n; ++i) {
let g = 0;
for (let j = i; j < n; ++j) {
g = gcd(g, nums[j]);
if (g === 1) {
mi = Math.min(mi, j - i + 1);
}
}
}
return mi > n ? -1 : n - 1 + mi - 1;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
|