【leetcode】1250. 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^5

1 <= nums[i] <= 10^9

解题思路：看到这个题目，大家或许能猜到这题对应着数学定律。至于是什么定律，我是不知道的。后来网上搜索才发现对应的定律是裴蜀定理，最后的解法就是求出所有元素的最大公约数，判断是否为1即可。

裴蜀定理（或贝祖定理，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成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1。

代码如下：

class Solution(object):

    def isGoodArray(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        def gcd(m, n):

            if not n:

                return m

            else:

                return gcd(n, m % n)

        val = nums[0]

        for i in range(1,len(nums)):

            val = gcd(val,nums[i])

        return val == 1

巴特西

【leetcode】1250. Check If It Is a Good Array

最新文章

热门文章