What does it mean for an array to be good in this problem?

An array is good if you can select a subset and assign integer multipliers to achieve a sum of 1.

Why is gcd the key concept for Check If It Is a Good Array?

Using number theory, a sum of 1 can be formed from integer combinations of array elements if and only if the gcd of all elements is 1.

Can I use brute-force subset enumeration?

No, enumerating all subsets is infeasible for large arrays. Use the gcd property for an efficient solution.

What is the time complexity of the optimal solution?

The time complexity is O(n log(max(nums))), iterating once through the array while updating the gcd.

How should negative multipliers be handled?

Negative multipliers are allowed implicitly in integer linear combinations, and the gcd check accounts for them without extra handling.

#1250

Hard

auto_awesome数组·数学

LeetCode 题解工作台

检查「好数组」

给你一个正整数数组 nums ，你需要从中任选一些子集，然后将子集中每一个数乘以一个任意整数，并求出他们的和。假如该和结果为 1 ，那么原数组就是一个「好数组」，则返回 True ；否则请返回 False 。示例 1：输入： nums = [12,5,7,23] 输出： true 解释…

数组数学数论

题目描述

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

lightbulb

解题思路

方法一：数学（裴蜀定理）

我们先可以考虑选取两个数的情况，若选取的数是 $a$ 和 $b$ ，那么根据题目的要求，我们需要满足 $a \times x + b \times y = 1$ ，其中 $x$ 和 $y$ 是任意整数。

根据裴蜀定理，可以得知，如果 $a$ 和 $b$ 互质，那么上述等式一定有解。实际上，裴蜀定理也可以推广到多个数的情况，即如果 $a_1, a_2, \cdots, a_i$ 互质，那么 $a_1 \times x_1 + a_2 \times x_2 + \cdots + a_i \times x_i = 1$ 一定有解，其中 $x_1, x_2, \cdots, x_i$ 是任意整数。

因此，我们只需要判断在数组 nums 中是否存在 $i$ 个互质的数即可。两个数互质的充要条件是它们的最大公约数为 $1$ 。如果数组 nums 存在 $i$ 个互质的数，那么数组 nums 中的所有数的最大公约数也为 $1$ 。

所以我们将题目转化为：判断数组 nums 中的所有数的最大公约数是否为 $1$ 。遍历数组 nums，求出数组 nums 中的所有数的最大公约数即可。

时间复杂度 $O(n + log m)$ ，空间复杂度 $O(1)$ ，其中 $n$ 是数组 nums 的长度，而 $m$ 是数组 nums 中的最大值。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	complexity is O(n log(max(nums))) due to iterative GCD calculations, where n is the array length and max(nums) the largest element. Space complexity is O(1) since only a running gcd needs storage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate quickly identifies the gcd property as the key insight.
question_mark
Watch for attempts to enumerate subsets or multipliers, which indicates misunderstanding of the number theory pattern.
question_mark
Confirm the candidate recognizes early exit when running gcd reaches 1.

warning

常见陷阱

外企场景

error
Attempting brute-force subset enumeration leading to timeout on large arrays.
error
Confusing positive integer sums with integer linear combinations, missing negative multipliers.
error
Ignoring the early exit opportunity when gcd becomes 1, causing unnecessary computations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Arrays containing negative numbers or zeros, which require adjusting gcd logic.
arrow_right_alt
Check if an array can generate a target other than 1 using integer multiples of a subset.
arrow_right_alt
Determine the minimal subset size needed to form 1, adding an optimization layer.

help

常见问题

外企场景

继续练习

#952 按公因数计算最大组件大小 #914 卡牌分组 #1627 带阈值的图连通性