LeetCode 1250 - Check If It Is a Good Array

LeetCode Problem 1250

Difficulty: 🔴 Hard
Topics: Array, Math, Number Theory

Solution

Problem Understanding

This problem asks whether it is possible to create the number 1 using the integers in the array, where each chosen number can be multiplied by any integer, including negative integers, before all results are summed together.

More formally, given an array nums, we want to know whether there exist integers:

$$x_1, x_2, x_3, \dots, x_n$$

such that:

$$nums[0] \cdot x_1 + nums[1] \cdot x_2 + \dots + nums[n-1] \cdot x_n = 1$$

The coefficients can be positive, negative, or zero. We are also allowed to ignore elements by multiplying them by 0.

The input consists of:

• An array of positive integers
• Array length up to 10^5
• Each value up to 10^9

The output should be:

• True if we can construct 1
• False otherwise

The constraints are extremely important here. Since the array can contain up to one hundred thousand numbers, any exponential or combinatorial search is impossible. Even quadratic solutions may become too slow. We need something close to linear time.

The key mathematical observation is that this problem is directly connected to Bézout's Identity from number theory.

Important edge cases include:

• Arrays with a single element
• Arrays where every number shares a common divisor greater than 1
• Arrays already containing 1
• Very large numbers
• Long arrays where the answer depends only on the cumulative greatest common divisor

For example:

• [1] is always good because 1 * 1 = 1
• [2,4,6] is not good because every combination remains divisible by 2
• [6,10,15] is good because their greatest common divisor is 1

Approaches

Brute Force Approach

A brute force solution would attempt to try all possible subsets and all possible integer coefficients for each chosen element.

For every subset, we could attempt combinations such as:

$$a_1x_1 + a_2x_2 + \dots + a_kx_k$$

and check whether any combination equals 1.

This approach is theoretically correct because it explores every valid construction allowed by the problem statement.

However, it is completely infeasible:

• There are 2^n subsets
• Each coefficient can be infinitely many integers
• The search space is unbounded

Even restricting coefficients to a limited range would still produce an exponential explosion.

This approach cannot work for n = 10^5.

Optimal Approach

The crucial insight comes from Bézout's Identity.

For any integers:

$$a_1, a_2, \dots, a_n$$

the set of all values obtainable through:

$$a_1x_1 + a_2x_2 + \dots + a_nx_n$$

is exactly the set of multiples of:

$$\gcd(a_1, a_2, \dots, a_n)$$

Therefore:

• We can form 1 if and only if the overall greatest common divisor of the array is 1
• If the gcd is greater than 1, every possible sum is divisible by that gcd, so forming 1 is impossible

So the entire problem reduces to computing:

$$\gcd(nums[0], nums[1], \dots, nums[n-1])$$

and checking whether it equals 1.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries subsets and coefficient combinations
Optimal	O(n log M)	O(1)	Computes cumulative gcd across the array

Here, M is the maximum value in the array.

Algorithm Walkthrough

Step 1: Initialize the running gcd

Start with the first number in the array as the current gcd.

This value will gradually shrink as we process more numbers.

Step 2: Iterate through the array

For each number:

1. Compute the gcd between the current gcd and the new number
2. Update the running gcd

Mathematically:

$$current_gcd = \gcd(current_gcd, nums[i])$$

This works because gcd is associative:

$$\gcd(a,b,c) = \gcd(\gcd(a,b),c)$$

Step 3: Early stopping optimization

If at any point the gcd becomes 1, we can immediately return True.

Once gcd reaches 1, adding more numbers cannot reduce it further.

Step 4: Return the result

After processing all elements:

• Return True if gcd is 1
• Otherwise return False

Why it works

Bézout's Identity guarantees that all integer linear combinations of the array elements are multiples of the array's gcd.

If the gcd equals 1, then some integer combination must produce 1.

If the gcd is greater than 1, every combination remains divisible by that gcd, so producing 1 is impossible.

Therefore, checking whether the array gcd equals 1 is both necessary and sufficient.

Python Solution

from typing import List
from math import gcd

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        current_gcd = 0

        for num in nums:
            current_gcd = gcd(current_gcd, num)

            if current_gcd == 1:
                return True

        return False

The implementation starts with current_gcd = 0. This is convenient because:

$$\gcd(0, x) = x$$

so the first iteration naturally initializes the running gcd.

The loop processes each number and continuously updates the cumulative gcd. The math.gcd function uses the Euclidean algorithm internally, which is extremely efficient.

An early return is used when the gcd becomes 1. Since gcd cannot decrease below 1, further processing becomes unnecessary.

Finally, if the loop finishes without reaching 1, the function returns False.

Go Solution

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func isGoodArray(nums []int) bool {
	currentGCD := 0

	for _, num := range nums {
		currentGCD = gcd(currentGCD, num)

		if currentGCD == 1 {
			return true
		}
	}

	return false
}

The Go implementation follows the same logic as the Python solution.

Since Go does not provide a built in gcd function for integers in the standard library, we implement the Euclidean algorithm manually.

The solution uses a running gcd variable and updates it while iterating through the slice.

Go integers safely handle the problem constraints because values are at most 10^9, which fits comfortably inside a standard int.

Worked Examples

Example 1

Input:

nums = [12,5,7,23]

Processing steps:

Step	Current Number	Running GCD
Start	-	0
1	12	gcd(0,12) = 12
2	5	gcd(12,5) = 1

The gcd becomes 1, so we immediately return True.

This matches the example expression:

$$5 \times 3 + 7 \times (-2) = 1$$

Example 2

Input:

nums = [29,6,10]

Processing steps:

Step	Current Number	Running GCD
Start	-	0
1	29	29
2	6	gcd(29,6) = 1

The gcd becomes 1, so the array is good.

A valid combination is:

$$29 \times 1 + 6 \times (-3) + 10 \times (-1) = 1$$

Example 3

Input:

nums = [3,6]

Processing steps:

Step	Current Number	Running GCD
Start	-	0
1	3	3
2	6	gcd(3,6) = 3

The final gcd is 3, not 1.

Every possible combination remains divisible by 3, so producing 1 is impossible.

Return False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log M)	Each gcd computation takes O(log M)
Space	O(1)	Only a few variables are used

The Euclidean algorithm computes gcd very efficiently. For each element, gcd computation takes logarithmic time relative to the magnitude of the numbers involved.

Since we process all n elements once, the total complexity becomes:

$$O(n \log M)$$

where M is the largest number in the array.

The algorithm uses constant extra space because it only stores the running gcd.

Test Cases

from typing import List
from math import gcd

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        current_gcd = 0

        for num in nums:
            current_gcd = gcd(current_gcd, num)

            if current_gcd == 1:
                return True

        return False

sol = Solution()

assert sol.isGoodArray([12, 5, 7, 23]) == True   # provided example, gcd becomes 1
assert sol.isGoodArray([29, 6, 10]) == True      # provided example
assert sol.isGoodArray([3, 6]) == False          # provided example, gcd is 3

assert sol.isGoodArray([1]) == True              # single element equal to 1
assert sol.isGoodArray([2]) == False             # single element not equal to 1

assert sol.isGoodArray([2, 4, 6, 8]) == False   # all even numbers
assert sol.isGoodArray([6, 10, 15]) == True     # cumulative gcd becomes 1

assert sol.isGoodArray([7, 14, 21]) == False    # common divisor 7
assert sol.isGoodArray([17, 19]) == True        # coprime primes

assert sol.isGoodArray([1000000000, 999999937]) == True  # large values
assert sol.isGoodArray([9, 27, 81]) == False             # powers of same base

assert sol.isGoodArray([18, 24, 35]) == True    # gcd eventually reduces to 1

Test Summary

Test	Why
[12,5,7,23]	Standard positive example
[29,6,10]	Another valid combination
[3,6]	Common divisor prevents success
[1]	Smallest valid good array
[2]	Single non-good element
[2,4,6,8]	All values share gcd 2
[6,10,15]	Pairwise interactions reduce gcd to 1
[7,14,21]	Larger common divisor
[17,19]	Two coprime primes
[1000000000,999999937]	Large constraint values
[9,27,81]	Powers sharing same gcd
[18,24,35]	Gcd gradually decreases to 1

Edge Cases

Single Element Arrays

A single number array can easily cause incorrect assumptions. For example:

[1]

is good because:

$$1 \times 1 = 1$$

However:

[7]

is not good because every multiple of 7 remains divisible by 7.

The implementation handles this naturally because the running gcd becomes the single value itself.

Arrays With a Common Divisor

Arrays like:

[4, 8, 12]

all share a gcd of 4.

A buggy implementation might incorrectly assume combining many numbers can eventually create 1, but Bézout's Identity proves every combination remains divisible by 4.

The gcd check guarantees correctness here.

Large Numbers

The constraints allow values up to 10^9.

A naive brute force approach attempting coefficient searches would become computationally impossible.

The Euclidean algorithm handles large values efficiently, since gcd computation runs in logarithmic time.

Even arrays with one hundred thousand large numbers remain manageable with this approach.