【Leetcode】1250. Check If It Is a Good Array

题目地址：

https://leetcode.com/problems/check-if-it-is-a-good-array/description/

给定一个长$n$数组$A$，其数为$x_{1\sim n}$，问是否$\exists x_1,x_2,...,x_k\in A,s.t.\exists c_1,...,c_k\in \mathbb{Z},{\sum }_{i=1}^k{c}_i{x}_i=1$。

$\exists c_1,...,c_k\in \mathbb{Z},{\sum }_{i=1}^k{c}_i{x}_i=1$等价于 gcd ⁡ { x 1 , . . . , x k } = 1 \gcd\{x_1,...,x_k\}=1 gcd{x1​,...,xk​}=1，而其能推出 gcd ⁡ { x 1 , . . . , x n } = 1 \gcd\{x_1,...,x_n\}=1 gcd{x1​,...,xn​}=1。如果 gcd ⁡ { x 1 , . . . , x n } = 1 \gcd\{x_1,...,x_n\}=1 gcd{x1​,...,xn​}=1那显然满足条件。所以只需要 gcd ⁡ { x 1 , . . . , x n } = 1 \gcd\{x_1,...,x_n\}=1 gcd{x1​,...,xn​}=1即可。求最大公约数可以用欧几里得算法。代码如下：

class Solution {
 public:
  bool isGoodArray(vector<int>& nums) {
    int x = nums[0];
    for (int a : nums) {
      x = gcd(x, a);
      if (x == 1) return true;
    }

    return false;
  }

  int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度$O({\sum }_i\log A_i)$，空间$O(1)$。