https://leetcode.com/problems/check-if-it-is-a-good-array/
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^51 <= nums[i] <= 10^9
Intuition
This problem is realated a Chinese theorem:
Chinese remainder theorem, created in 5th centry.
Also well known as Hanson Counting (韩信点兵).
Chinese remainder theorem, created in 5th centry.
Also well known as Hanson Counting (韩信点兵).
Explanation
If
appareantly we have
If
a % x = 0 and b % x = 0,appareantly we have
(pa + qb) % x == 0If
x > 1, making it impossible pa + qb = 1.
Well, I never heard of Bezout's identity.
Even though the intuition only proves the necessary condition,
it's totally enough.
Even though the intuition only proves the necessary condition,
it's totally enough.
The process of gcd,
is exactly the process to get the factor.
The problem just doesn't ask this part.
is exactly the process to get the factor.
The problem just doesn't ask this part.
Complexity
Of course you can return true as soon as
I take gcd calculate as
gcd = 1I take gcd calculate as
O(1).
Time
Space
O(N)，Space
O(N) public boolean isGoodArray(int[] A) {
int x = A[0], y;
for (int a: A) {
while (a > 0) {
y = x % a;
x = a;
a = y;
}
}
return x == 1;
}
Read (https://brilliant.org/wiki/bezouts-identity/, https://en.wikipedia.org/wiki/Bézout's_identity)
The basic idea is that for integers a and b, if gcd(a,b) = d, then there exist integers x and y, s.t a * x + b * y = d;
This can be generalized for (n >= 2) . e.g. if gcd(a,b,c) = d, then there exist integers x, y, and z, s.t, a* x + b*y + c * z = d.
Now this problem is just asking if gcd(x1, ......, xn) = 1
class Solution {
public:
bool isGoodArray(vector<int>& nums) {
if (nums.size() == 1) return nums[0] == 1;
int a = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (__gcd(a, nums[i]) == 1) return true;
a = __gcd(a, nums[i]);
}
return false;
}
解题思路：看到这个题目，大家或许能猜到这题对应着数学定律。至于是什么定律，我是不知道的。后来网上搜索才发现对应的定律是裴蜀定理，最后的解法就是求出所有元素的最大公约数，判断是否为1即可。
https://www.cnblogs.com/wentiliangkaihua/p/11870419.html裴蜀定理（或贝祖定理，Bézout's identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
找最大公约数是不是1.
辗转相除法：第二次开始一直用除数除以余数，知道余数为0，当前除数就是最大公约数。
看起来最后返回的是除数，但其实应该是被除数
public static int gcd(int a, int b){ int c = a % b; while(c > 0){ c = a % b; a = b; b = c; } return a; }
因为最后一步把b赋给a了，然后b其实==0.
最后写了种自己能写的方法
int x = nums[0]; for(int i = 0; i < nums.length; i++){ x = gcd(x, nums[i]); } return x == 1; } public int gcd(int a, int b){ int c = a % b; while(c > 0){ c = a % b; a = b; b = c; } return a; }
