1250. Check If It Is a Good Array
Description
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
Solutions
Solution 1: Mathematics (Bézout's Identity)
First, consider the situation where we select two numbers. If the selected numbers are $a$ and $b$, then according to the problem's requirements, we need to satisfy $a \times x + b \times y = 1$, where $x$ and $y$ are any integers.
According to Bézout's Identity, if $a$ and $b$ are coprime, then the above equation definitely has a solution. In fact, Bézout's Identity can also be extended to the case of multiple numbers. That is, if $a_1, a_2, \cdots, a_i$ are coprime, then $a_1 \times x_1 + a_2 \times x_2 + \cdots + a_i \times x_i = 1$ definitely has a solution, where $x_1, x_2, \cdots, x_i$ are any integers.
Therefore, we only need to determine whether there exist $i$ coprime numbers in the array nums
. The necessary and sufficient condition for two numbers to be coprime is that their greatest common divisor is $1$. If there exist $i$ coprime numbers in the array nums
, then the greatest common divisor of all numbers in the array nums
is also $1$.
So we transform the problem into: determining whether the greatest common divisor of all numbers in the array nums
is $1$. We can do this by traversing the array nums
and finding the greatest common divisor of all numbers in the array nums
.
The time complexity is $O(n + \log m)$, and the space complexity is $O(1)$. Where $n$ is the length of the array nums
, and $m$ is the maximum value in the array nums
.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 |
|