Is Check If It Is a Good Array easy or hard?

The problem is labeled Hard on LeetCode because recognizing the Bézout identity connection is not obvious at first. Once you identify that the condition reduces to checking whether the array GCD equals 1, the implementation becomes short and efficient.

Check If It Is a Good Array Python/Java solution

In Python or Java, iterate through the array and repeatedly compute the GCD using built-in functions such as math.gcd in Python or a custom gcd method in Java. Maintain a running GCD variable and check if the final value equals 1.

How to solve Check If It Is a Good Array in O(n)?

The solution iterates once through the array while maintaining a running GCD value. For each element, update gcd = gcd(gcd, nums[i]). Although the loop is O(n), each GCD operation costs O(log M), making the full complexity O(n log M). If the final GCD equals 1, return true.

What is the best approach for Check If It Is a Good Array?

The best approach is computing the greatest common divisor (GCD) of all elements in the array. According to Bézout's Identity, a linear combination of the numbers can equal 1 if and only if their GCD is 1. Iterate through the array and keep updating the GCD. If the final result equals 1, the array is a Good Array.

Is Check If It Is a Good Array asked at Google/Amazon/Meta?

Problems involving GCD properties and Bézout's identity frequently appear in interviews at companies like Google, Amazon, and Meta. They test knowledge of number theory fundamentals and the ability to reduce a mathematical condition to a simple algorithmic check.

What data structure is used in Check If It Is a Good Array?

The problem primarily uses an array for input storage and relies on mathematical operations rather than complex data structures. The key algorithmic tool is the Euclidean algorithm for computing the greatest common divisor.

What is the time complexity of Check If It Is a Good Array?

The optimal solution runs in O(n log M) time, where n is the number of elements and M is the maximum value in the array. Each step computes a GCD using the Euclidean algorithm, which takes O(log M). Space complexity remains O(1) because only a running GCD variable is maintained.

Description Hints 2 Solution Video 4:17

1250. Check If It Is a Good Array

Hard65.6% acceptance5 companies

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

Asked at 5 companies

Dropbox

Nokia American Express

Google Microsoft

Topics

Hints open one at a time

Hint 1

Eq. ax+by=1 has solution x, y if gcd(a,b) = 1.

Hint 2

Can you generalize the formula?. Check Bézout's lemma.

4:17

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[12,5,7,23]

Input

[29,6,10]

Input

[3,6]

Your code is saved on this device.Solution