1250. Check If It Is a Good Array

Problem

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.

https://leetcode.com/problems/check-if-it-is-a-good-array/

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⁵
• 1 <= nums[i] <= 10⁹

Test Cases

1
2

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('nums, expected', [
    ([12,5,7,23], True),
    ([29,6,10], True),
    ([3,6], False),

    ([1], True),
    ([2], False),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, nums, expected):
    assert sol.isGoodArray(nums) == expected

Thoughts

这是道数学题。有个「裴蜀定理」（Bézout’s identity），说对于任何整数 a、b 和 m，关于未知数 x 和 y 的 线性丢番图方程（Diophantine equation）（称为裴蜀等式）a*x + b*y = m 有整数解当且仅当 m 是 a 和 b 的最大公约数 d 的倍数。特别地，方程 a*x + b*y = 1 有整数解当且仅当整数 a 和 b 互质。

所以至少 nums 中有一对互质数，结果就为 True。可以直接计算 nums 中所有数字共同的最大公约数，如果为 1 则结果为 True，否则为 False。

Python 里 math.gcd 方法可以直接计算一组数字的最大公约数。

如果不想用自带的函数，也可以自己实现 gcd(a, b)，通过辗转相除法计算 a 和 b 的最大公约数。将结果再与数组中下一个数求最大公约数，循环一遍就得到所有数字的最大公约数。

Code

1
2
3
4
5
6

from math import gcd


class Solution:
    def isGoodArray(self, nums: list[int]) -> bool:
        return gcd(*nums) == 1

1
2
3
4
5
6
7
8
9
10

from functools import reduce


class Solution:
    def isGoodArray(self, nums: list[int]) -> bool:
        def _gcd(a: int, b: int) -> int:
            while a % b > 0: a, b = b, a % b
            return b

        return reduce(_gcd, nums) == 1

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章