Check If It Is a Good Array solution and explanation
Nokia
Google
8 more videos on this problem
1250. Check If It Is a Good Array || leetcode HARD || [ C++ SOLUTION ]code Explainer · 4:17 · 3K views
Leetcode 1250: Check If It Is a Good ArrayAlgorithms Casts · 8:35 · 2K views
1250. Check If It Is a Good Array | Java | Leetcode | Number Theory | DSACoding with Tamilarasan · 4:42 · 796 views
1250. Check If It Is a Good ArrayMath Geeks · 6:55 · 549 views
Check If It Is a Good Array | LeetCode 1250 | Hard ProblemRajan Jha · 6:06 · 534 views
Check If It Is a Good Array (LeetCode 1250 Hard) | Bézout’s Identity & GCD ExplainedYash Poonia · 13:04 · 480 views
Leetcode 1250. Check If It Is a Good ArrayFearless Learner · 3:54 · 246 views
LeetCode 1250: Check If It Is a Good ArrayAlitaCode · 26:01 · 5 views
No Sound Leetcode 1250: Check if it is a Good ArrayExtremeProgrammer · 0:38 · 3 views
The problem
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^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.
from math import gcd
from functools import reduce
def isGoodArray(nums):
currentGCD = reduce(gcd, nums)
return currentGCD == 1
nums = [12, 5, 7, 23]
print(isGoodArray(nums))import java.util.*;
public class GoodArray {
public static boolean isGoodArray(int[] nums) {
int currentGCD = nums[0];
for (int i = 1; i < nums.length; i++) {
currentGCD = gcd(currentGCD, nums[i]);
if (currentGCD == 1) return true;
}
return currentGCD == 1;
}
private static int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
public static void main(String[] args) {
int[] nums = {12, 5, 7, 23};
System.out.println(isGoodArray(nums));
}
}#include <iostream>
#include <vector>
#include <numeric>
bool isGoodArray(std::vector<int>& nums) {
int currentGCD = nums[0];
for (int i = 1; i < nums.size(); ++i) {
currentGCD = std::gcd(currentGCD, nums[i]);
if (currentGCD == 1) return true;
}
return currentGCD == 1;
}
int main() {
std::vector<int> nums = {12, 5, 7, 23};
std::cout << (isGoodArray(nums) ? "true" : "false") << std::endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
let t = b;
b = a % b;
a = t;
}
return a;
}
function isGoodArray(nums) {
let currentGCD = nums[0];
for (let i = 1; i < nums.length; i++) {
currentGCD = gcd(currentGCD, nums[i]);
if (currentGCD === 1) return true;
}
return currentGCD === 1;
}
const nums = [12, 5, 7, 23];
console.log(isGoodArray(nums));#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int isGoodArray(int* nums, int numsSize) {
int currentGCD = nums[0];
for (int i = 1; i < numsSize; i++) {
currentGCD = gcd(currentGCD, nums[i]);
if (currentGCD == 1) {
return 1;
}
}
return currentGCD == 1;
}
int main() {
int nums[] = {12, 5, 7, 23};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%s\n", isGoodArray(nums, size) ? "true" : "false");
return 0;
}using System;
public class Program
{
public static bool IsGoodArray(int[] nums)
{
int currentGCD = nums[0];
for (int i = 1; i < nums.Length; i++)
{
currentGCD = GCD(currentGCD, nums[i]);
if (currentGCD == 1) return true;
}
return currentGCD == 1;
}
private static int GCD(int a, int b)
{
while (b != 0)
{
int t = b;
b = a % b;
a = t;
}
return a;
}
public static void Main()
{
int[] nums = { 12, 5, 7, 23 };
Console.WriteLine(IsGoodArray(nums));
}
}The Python solution uses the reduce function along with gcd from the math library to compute the GCD of the entire array efficiently.
Time Complexity: O(n * log(max(nums[i])))
Space Complexity: O(1)
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.
def gcd_extended(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = gcd_extended(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
def isGoodArray(nums):
gcd_value, x, y = gcd_extended(nums[0], nums[1])
for i in range(2, len(nums)):
gcd_value, x, y = gcd_extended(gcd_value, nums[i])
if gcd_value == 1:
return True
return gcd_value == 1
nums = [12, 5, 7, 23]
print(isGoodArray(nums))public class GoodArray {
public static int gcdExtended(int a, int b, int[] x, int[] y) {
if (b == 0) {
x[0] = 1;
y[0] = 0;
return a;
}
int[] x1 = {0}, y1 = {0};
int gcd = gcdExtended(b, a % b, x1, y1);
x[0] = y1[0];
y[0] = x1[0] - (a / b) * y1[0];
return gcd;
}
public static boolean isGoodArray(int[] nums) {
int gcd = nums[0];
for (int i = 1; i < nums.length; i++) {
int[] x = {0}, y = {0};
gcd = gcdExtended(gcd, nums[i], x, y);
if (gcd == 1) return true;
}
return gcd == 1;
}
public static void main(String[] args) {
int[] nums = {12, 5, 7, 23};
System.out.println(isGoodArray(nums));
}
}#include <iostream>
#include <vector>
void extendedGCD(int a, int b, int &x, int &y, int &g) {
if (b == 0) {
g = a;
x = 1;
y = 0;
return;
}
int x1, y1;
extendedGCD(b, a % b, x1, y1, g);
x = y1;
y = x1 - (a / b) * y1;
}
bool isGoodArray(std::vector<int>& nums) {
int x, y, gcd_value;
extendedGCD(nums[0], nums[1], x, y, gcd_value);
for (int i = 2; i < nums.size(); ++i) {
extendedGCD(gcd_value, nums[i], x, y, gcd_value);
if (gcd_value == 1) return true;
}
return gcd_value == 1;
}
int main() {
std::vector<int> nums = {12, 5, 7, 23};
std::cout << (isGoodArray(nums) ? "true" : "false") << std::endl;
return 0;
}function gcdExtended(a, b, x, y) {
if (a === 0) {
x[0] = 0;
y[0] = 1;
return b;
}
let x1 = [0], y1 = [0];
let gcd = gcdExtended(b % a, a, x1, y1);
x[0] = y1[0] - Math.floor(b / a) * x1[0];
y[0] = x1[0];
return gcd;
}
function isGoodArray(nums) {
let x = [0], y = [0];
let gcd_value = gcdExtended(nums[0], nums[1], x, y);
for (let i = 2; i < nums.length; i++) {
gcd_value = gcdExtended(gcd_value, nums[i], x, y);
if (gcd_value === 1) return true;
}
return gcd_value === 1;
}
const nums = [12, 5, 7, 23];
console.log(isGoodArray(nums));#include <stdio.h>
void extendedGCD(int a, int b, int* x, int* y, int* gcd) {
if (b == 0) {
*gcd = a;
*x = 1;
*y = 0;
return;
}
int x1, y1;
extendedGCD(b, a % b, &x1, &y1, gcd);
*x = y1;
*y = x1 - (a / b) * y1;
}
int isGoodArray(int* nums, int numsSize) {
int x, y, gcd_value;
extendedGCD(nums[0], nums[1], &x, &y, &gcd_value);
for (int i = 2; i < numsSize; i++) {
extendedGCD(gcd_value, nums[i], &x, &y, &gcd_value);
if (gcd_value == 1) return 1;
}
return gcd_value == 1;
}
int main() {
int nums[] = {12, 5, 7, 23};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%s\n", isGoodArray(nums, size) ? "true" : "false");
return 0;
}using System;
public class Program
{
private static int GCDExtended(int a, int b, ref int x, ref int y)
{
if (a == 0) {
x = 0;
y = 1;
return b;
}
int x1 = 0, y1 = 0;
int gcd = GCDExtended(b % a, a, ref x1, ref y1);
x = y1 - (b / a) * x1;
y = x1;
return gcd;
}
public static bool IsGoodArray(int[] nums)
{
int x = 0, y = 0;
int gcd = nums[0];
for (int i = 1; i < nums.Length; i++)
{
gcd = GCDExtended(gcd, nums[i], ref x, ref y);
if (gcd == 1) return true;
}
return gcd == 1;
}
public static void Main()
{
int[] nums = { 12, 5, 7, 23 };
Console.WriteLine(IsGoodArray(nums));
}
}In this Python solution, the extended Euclidean function discovers coefficients even if they aren't mandatory in determining solution possible.
Time Complexity: O(n * log(max(nums[i])))
Space Complexity: O(1)
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.
function isGoodArray(nums: number[]): boolean {
return nums.reduce(gcd) === 1;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func isGoodArray(nums []int) bool {
g := 0
for _, x := range nums {
g = gcd(x, g)
}
return g == 1
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using GCD | Time Complexity: O(n * log(max(nums[i]))) |
| Using Extended Euclidean Algorithm (Conceptual) | Time Complexity: O(n * log(max(nums[i]))) |
| Mathematics (Bézout's Identity) | – |
Complexity analysis
| 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 |
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.