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.
The array is good if we can form 1 as a linear combination of the numbers with integer coefficients. By Bézout’s identity, this is possible if and only if the greatest common divisor (GCD) of the array is 1.
classSolution {
public:bool isGoodArray(vector<int>& nums) {
int g = nums[0];
for (int x : nums) g = gcd(g, x);
return g ==1;
}
intgcd(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
funcisGoodArray(nums []int) bool {
g:=nums[0]
gcd:=func(a, bint) int {
forb!=0 {
a, b = b, a%b }
returna }
for_, x:=rangenums {
g = gcd(g, x)
}
returng==1}
1
2
3
4
5
6
7
8
9
10
classSolution {
publicbooleanisGoodArray(int[] nums) {
int g = nums[0];
for (int x : nums) g = gcd(g, x);
return g == 1;
}
privateintgcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
1
2
3
4
5
6
7
8
classSolution {
funisGoodArray(nums: IntArray): Boolean {
fungcd(a: Int, b: Int): Int = if (b ==0) a else gcd(b, a % b)
var g = nums[0]
for (x in nums) g = gcd(g, x)
return g ==1 }
}
1
2
3
4
5
6
7
classSolution:
defisGoodArray(self, nums: list[int]) -> bool:
from math import gcd
g = nums[0]
for x in nums:
g = gcd(g, x)
return g ==1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnis_good_array(nums: Vec<i32>) -> bool {
fngcd(mut a: i32, mut b: i32) -> i32 {
while b !=0 {
let t = b;
b = a % b;
a = t;
}
a
}
letmut g = nums[0];
for&x in&nums {
g = gcd(g, x);
}
g ==1 }
}