How to Solve Check If It Is a Good Array

This problem requires verifying if a sum of 1 can be formed from integer multiples of any subset of the array. Using the gcd property from number theory, the array is good if the gcd of all elements is 1. Focus on efficiently computing gcd across potentially large arrays to handle the Hard constraints.

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. 53 + 7(-2) = 1

Example 2

Input: nums = [29,6,10]

Output: true

Pick numbers 29, 6 and 10. 291 + 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

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.

How GhostInterview Helps

• Provides direct identification of the gcd pattern relevant to integer linear combinations.
• Highlights the exact subset-plus-multiplier failure mode, preventing brute-force mistakes.
• Offers step-by-step guidance on efficiently iterating through large arrays to compute gcd.

Topic Pages

• Array
• Math
• Number Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.