Algorithm (Math)

First, we observe the following elementary number theory result.

Proposition. Let $a_{1},…,a_{n}$ be integers. Then $\text{gcd}(a_{1},…,a_{n})=1$ if and only if there exists $x_{1},…,x_{n}$ such that $\sum_{i}x_{i}a_{i}=1.$

Proof. See here

Therefore, this problem is reduced to checking if there exists $a_{1},…,a_{m}\in\text{nums}$ such that $\text{gcd}(a_{1},…,a_{m})=1.$

Code

class Solution {
 public:
  bool isGoodArray(vector<int>& nums) {
    return std::accumulate(begin(nums), end(nums), nums[0], [&](auto x, auto y) {
      return gcd(x, y);
    }) == 1;

  }
};