Watch 10 video solutions for Check If It Is a Good Array, a hard level problem involving Array, Math, Number Theory. This walkthrough by code Explainer has 3,004 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |