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^51 <= nums[i] <= 10^9Problem 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.
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.
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.
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.
Time Complexity: O(n * log(max(nums[i])))
Space Complexity: O(1)
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using GCD | Time Complexity: O(n * log(max(nums[i]))), where n is the number of elements in the array. |
| Using Extended Euclidean Algorithm (Conceptual) | Time Complexity: O(n * log(max(nums[i]))) |
| Mathematics (Bézout's Identity) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative GCD Across Array | O(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 |
1250. Check If It Is a Good Array || leetcode HARD || [ C++ SOLUTION ] • code Explainer • 3,004 views views
Watch 9 more video solutions →Practice Check If It Is a Good Array with our built-in code editor and test cases.
Practice on FleetCode