Skip to main content
Talentd

Check If It Is a Good Array - Solution & Explanation

HardArrayMathNumber Theory22 min readAsked at: Microsoft, American Express, Nokia +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array nums. The array is considered good if it is possible to pick integers x1, x2, ... xn such that nums[0]*x1 + nums[1]*x2 + ... + nums[n-1]*xn = 1. The task is to determine whether such a combination exists.

Approach 1: Using GCD (Optimal) (Time: O(n log M), Space: O(1))

The key observation comes from Bézout's Identity in number theory. A linear combination of integers can produce 1 if and only if the greatest common divisor (GCD) of those integers is 1. Instead of searching for coefficients x1..xn, compute the GCD of the entire array. Iterate through the array and continuously update the running GCD using the Euclidean algorithm. If the final GCD equals 1, the array is good; otherwise it is not. This works because any integer linear combination of the numbers must be a multiple of their GCD.

This approach uses simple iteration over the array and repeated GCD calculations. Each GCD operation takes O(log M) where M is the maximum number value. The total complexity becomes O(n log M), which is optimal for this problem and works efficiently even for large inputs.

Approach 2: Extended Euclidean Algorithm (Conceptual) (Time: O(n log M), Space: O(1))

The Extended Euclidean Algorithm explicitly computes integers x and y such that ax + by = gcd(a, b). By repeatedly applying this idea across the array, you can construct coefficients that represent the GCD as a linear combination of all numbers. If the final GCD becomes 1, the coefficients produced by the algorithm directly prove the existence of integers that satisfy the required equation.

In practice, you usually do not need to compute the actual coefficients. The existence condition is enough, so checking whether the cumulative GCD equals 1 is sufficient. The extended algorithm mainly provides the mathematical justification behind the optimal solution and is a classic concept in math and cryptography.

Recommended for interviews: The GCD reduction approach is what interviewers expect. It demonstrates recognition of the Bézout identity and avoids unnecessary brute force attempts over coefficients. Mentioning the Extended Euclidean Algorithm shows deeper understanding of the underlying mathematics.

Approach 1: Using GCD

The key to solving this problem lies in understanding the mathematical concept of GCD (Greatest Common Divisor). According to Bezout's Identity, for any integers a and b, there exist integers x and y such that ax + by = gcd(a, b). This can be extended to multiple integers. Hence, the array is 'good' if we can reduce it to a GCD of 1 using any subset. If the GCD of the entire array is 1, then you can express 1 as a combination of elements in the array. Otherwise, it's impossible. Calculate the GCD of all numbers in the array and return true if it is 1, false otherwise.

This solution calculates the GCD of the entire array. It starts with the first element and iteratively updates the current GCD with each element in the array. If at any point the GCD becomes 1, we can immediately return true because we know 1 is obtainable.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log(max(nums[i]))), where n is the number of elements in the array.
Space Complexity: O(1), as we are only using a fixed amount of space.

Try this approach in the editor →

Approach 2: Using Extended Euclidean Algorithm (Conceptual)

Another conceptual approach involves using the extended Euclidean algorithm to explicitly find coefficients (though not necessary to solve the problem). The essence is the same; we are validating whether these coefficients can sum up to yield 1. Finding explicit coefficients is not needed if we're checking the GCD, but it underpins the theory.

This solution computes explicit coefficients using the extended Euclidean algorithm to conceptually check the problem's requirements. However, for our particular use case, determining GCD suffices without explicit coefficients.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log(max(nums[i])))
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: 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.

According to Bézout's Identity, if a and b are coprime, then the above equation definitely has a solution. In fact, Bézout's Identity can also be extended to the case of multiple numbers. That is, if a_1, a_2, cdots, a_i are coprime, then a_1 times x_1 + a_2 times x_2 + cdots + a_i times x_i = 1 definitely has a solution, where x_1, x_2, cdots, x_i are any integers.

Therefore, we only need to determine whether there exist i coprime numbers in the array nums. The necessary and sufficient condition for two numbers to be coprime is that their greatest common divisor is 1. If there exist i coprime numbers in the array nums, then the greatest common divisor of all numbers in the array nums is also 1.

So we transform the problem into: determining whether the greatest common divisor of all numbers in the array nums is 1. We can do this by traversing the array nums and finding the greatest common divisor of all numbers in the array nums.

The time complexity is O(n + log m), and the space complexity is O(1). Where n is the length of the array nums, and m is the maximum value in the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using GCD

Time Complexity: O(n * log(max(nums[i]))), where n is the number of elements in the array.
Space Complexity: O(1), as we are only using a fixed amount of space.

Using Extended Euclidean Algorithm (Conceptual)

Time Complexity: O(n * log(max(nums[i])))
Space Complexity: O(1)

Mathematics (Bézout's Identity)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative GCD Across ArrayO(n log M)O(1)Best general solution; efficient for all constraints
Extended Euclidean Algorithm (Conceptual)O(n log M)O(1)Useful for understanding the mathematical proof and coefficient construction

Video Solution

1250. Check If It Is a Good Array || leetcode HARD || [ C++ SOLUTION ] • code Explainer • 3,062 views views

Watch 8 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Check If It Is a Good Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays