Problem Description

The Leetcode problem "Check If It Is a Good Array" provides you with an array of positive integers called nums. The task is to determine whether it is possible to select some (possibly all) elements from nums and assign them integer multipliers (which can be negative, zero, or positive), such that their linear combination sums to exactly 1.

Formally, you want to check if there exist integers x_1, x_2, ..., x_n (some of which may be zero) such that:

x_1 * nums[0] + x_2 * nums[1] + ... + x_n * nums[n-1] = 1

Constraints:

• Each element in nums is a positive integer.
• The array may be of any length.
• You may use any integer multipliers, including negative numbers and zero.

Thought Process

At first glance, the problem seems to invite a brute-force approach: try all possible combinations of elements and multipliers to see if you can form 1. However, this quickly becomes infeasible for large arrays due to the vast number of possibilities.

Upon closer inspection, the problem is a classic number theory question: can 1 be written as an integer linear combination of the numbers in nums? This is directly related to the concept of the greatest common divisor (GCD). The set of all integer linear combinations of a given set of integers is exactly the set of all multiples of their GCD.

Therefore, if the GCD of all numbers in nums is 1, then 1 can be formed as an integer linear combination of those numbers. If the GCD is greater than 1, then only multiples of that GCD can be formed, and 1 is not among them.

This realization lets us avoid brute force, and focus on a single GCD computation.

Solution Approach

To solve the problem efficiently, we use the following steps:

1. Compute the GCD of the entire array:
   • Start with the first element as your initial GCD.
   • Iteratively compute the GCD of the current GCD and the next element in the array.
   • Repeat this process until all elements have been processed.
2. Check if the GCD is 1:
   • If the final GCD is 1, return True (it is a "good" array).
   • Otherwise, return False.

This approach is highly efficient because computing the GCD of two numbers is a fast operation (using the Euclidean algorithm), and we only need to process each element once.

Example Walkthrough

Let's walk through an example with nums = [12, 5, 7, 23]:

1. Start with gcd = 12.
2. Compute gcd(12, 5) = 1.
3. Now gcd = 1. Since the GCD is already 1, you can stop early (though the algorithm may continue).
4. Even if you continue: gcd(1, 7) = 1, gcd(1, 23) = 1.
5. Final GCD is 1, so the answer is True.

Why? Because any integer linear combination of these numbers can produce 1, thanks to the GCD being 1.

Another example: nums = [6, 10, 15]

1. Start with gcd = 6.
2. gcd(6, 10) = 2.
3. gcd(2, 15) = 1.
4. Final GCD is 1, so the answer is True.

But for nums = [4, 6, 8]:

1. gcd(4, 6) = 2.
2. gcd(2, 8) = 2.
3. Final GCD is 2, so the answer is False.

Here, you can only form even numbers as integer combinations, never 1.

Time and Space Complexity

Brute-force approach:

• Would require trying all combinations of elements and multipliers, which is exponential in the number of elements (not feasible for large arrays).

• Time Complexity: O(n \cdot \log M), where n is the length of nums and M is the largest element. This is because each GCD computation takes O(\log M) time, and we do it n-1 times.
• Space Complexity: O(1), since we only store the current GCD and a few loop variables.

This makes the solution very efficient and scalable.

Code Implementation

from math import gcd
from functools import reduce

class Solution:
    def isGoodArray(self, nums):
        return reduce(gcd, nums) == 1
      

#include <vector>
#include <numeric>
using namespace std;

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int g = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            g = gcd(g, nums[i]);
            if (g == 1) return true;
        }
        return g == 1;
    }
};
      

class Solution {
    public boolean isGoodArray(int[] nums) {
        int g = nums[0];
        for (int i = 1; i < nums.length; i++) {
            g = gcd(g, nums[i]);
            if (g == 1) return true;
        }
        return g == 1;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}
      

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isGoodArray = function(nums) {
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    let g = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        g = gcd(g, nums[i]);
        if (g === 1) return true;
    }
    return g === 1;
};
      

Summary

The "Check If It Is a Good Array" problem is a great example of how number theory can simplify what appears to be a complex combinatorial task. By recognizing the connection to the greatest common divisor, we reduce the problem to a single pass through the array, checking if the GCD is 1. This approach is elegant, efficient, and leverages deep mathematical insight, making it a valuable technique for similar problems in coding interviews and algorithmic challenges.