1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
// 1250. Check If It Is a Good Array
#include <stdbool.h>
#include <stdio.h>
/*
* 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'
*/
int gcd(int a, int b) {
if (!a)
return b;
return gcd(b % a, a);
}
bool isGoodArray(int *nums, int nums_size) {
if (nums_size == 1)
return (nums[0] == 1);
int flag = gcd(nums[0], nums[1]);
for (int i = 2; i < nums_size; i++)
flag = gcd(flag, nums[i]);
return flag == 1;
}
int main() {
int n1[] = {12, 5, 7, 23}, n2[] = {29, 6, 10}, n3[] = {3, 6};
printf("%d\n", isGoodArray(n1, 4)); // expect: 1
printf("%d\n", isGoodArray(n2, 3)); // expect: 1
printf("%d\n", isGoodArray(n3, 2)); // expect: 0
}
|