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
Solution: Math
Bézout’s lemma: b[1] * A[1] + b[2] * A[2] + …. + b[n] * A[n] = 1 <==> gcd(A[1], A[2], …, A[n]) = 1 <=> at least two numbers are co-prime
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: bool isGoodArray(vector<int>& nums) { int g = nums[0]; for (int x : nums) g = gcd(g, x); return g == 1; } }; |