1250

1250. Check If It Is a Good Array (Hard)

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

 

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

 

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

Companies:
Dropbox

Related Topics:
Array, Math, Number Theory

Solution 1. Bézout's identity

https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity#For_three_or_more_integers

If $\gcd(a_1, a_2, \ldots, a_n) = d$, then there are integers $x_{1},x_{2},\ldots ,x_{n}$ such that

$$ d=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n} $$

has the following properties:

• $d$ is the smallest positive integer of this form
• every number of this form is a multiple of $d$

// OJ: https://leetcode.com/problems/check-if-it-is-a-good-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isGoodArray(vector<int>& A) {
        int d = A[0];
        for (int i = 1; i < A.size(); ++i) {
            d = gcd(d, A[i]);
        }
        return d == 1;
    }
};