#1250

Hard

LeetCode Problem Workspace

Check If It Is a Good Array

Determine if a given array of positive integers can generate 1 using integer multiples of any subset, leveraging number theory.

array math number theory

Problem Statement

Given an array nums of positive integers, determine whether it is possible to select a subset and assign integer multipliers so that the sum equals 1. The array is considered good if such a combination exists.

Return true if the array is good; otherwise, return false. For example, given nums = [12,5,7,23], picking 5 and 7 with multipliers 3 and -2 produces 1, so the output is true.

Examples

Example 1

Input: nums = [12,5,7,23]

Output: true

Pick numbers 5 and 7. 5 3 + 7(-2) = 1

Example 2

Input: nums = [29,6,10]

Output: true

Pick numbers 29, 6 and 10. 29 1 + 6(-3) + 10*(-1) = 1

Example 3

Input: nums = [3,6]

Output: false

Example details omitted.

Constraints

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

Solution Approach

Use Greatest Common Divisor (GCD)

Compute the gcd of all elements in the array. If the gcd equals 1, the array is good because integer linear combinations can produce 1 according to Bezout's identity. Otherwise, it is impossible.

Iterative GCD Computation

Iterate through the array, updating a running gcd. Early exit if the gcd becomes 1. This approach is efficient for large arrays up to 10^5 elements and avoids unnecessary calculations.

Avoid Unnecessary Subset Enumeration

Do not attempt brute-force checking of all subsets or multiplier combinations, as this is computationally infeasible. Focus solely on the mathematical property that gcd 1 guarantees a solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

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.

1

2

3

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

Continue Practicing

#952 largest component size by common factor #914 x of a kind in a deck of cards #1627 graph connectivity with threshold