# Check If It Is a Good Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-it-is-a-good-array)
Canonical: https://scaleengineer.com/dsa/problems/check-if-it-is-a-good-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Nokia](https://scaleengineer.com/companies/nokia), [Jump Trading](https://scaleengineer.com/companies/jump-trading)
---
## 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^5`
* `1 <= nums[i] <= 10^9`

# Approaches
## Prime Factorization Approach
This approach determines if the array is 'good' by calculating the greatest common divisor (GCD) of all its elements using prime factorization. Based on Bézout's identity, a linear combination of numbers can sum to 1 if and only if their GCD is 1. The array is good if the GCD of all its elements is 1. This method finds common prime factors among all numbers to compute their GCD.
**Time:** O(sqrt(M) + N * k), where N is the number of elements in the array, M is the value of the first element `nums[0]`, and k is the number of distinct prime factors of `nums[0]`. This is generally slower than the Euclidean algorithm approach. · **Space:** O(k), where k is the number of distinct prime factors of `nums[0]`. This space is used to store the common prime factors.
**Pros:** Provides a solution based on the fundamental theorem of arithmetic, illustrating the concept of GCD through prime factors.
**Cons:** Significantly less efficient than using the Euclidean algorithm, especially for large numbers.; Prime factorization is computationally expensive.; The implementation is more complex.
### Explanation
The problem asks if we can find a subset of `nums` and integer multipliers to form a sum of 1. This is a classic problem related to Bézout's identity, which states that an integer linear combination of numbers `a_1, a_2, ..., a_k` can equal their greatest common divisor (GCD). To get a sum of 1, the GCD of the chosen subset must be 1.
A key property is that for any subset `S` of `nums`, `gcd(S)` must be a multiple of `gcd(nums)`. Therefore, if we can find a subset with GCD 1, the GCD of the entire array must also be 1. Conversely, if `gcd(nums) = 1`, we can simply choose the whole array as our subset. The problem thus reduces to checking if `gcd(nums) == 1`.

This approach computes the GCD by finding common prime factors. It's less efficient but demonstrates the concept from first principles. The algorithm finds the prime factors of the first number and then iteratively filters this set by checking divisibility against subsequent numbers. If the set of common prime factors becomes empty, the GCD is 1.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    private Set<Integer> getPrimeFactors(int n) {
        Set<Integer> factors = new HashSet<>();
        if (n == 1) return factors;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

    public boolean isGoodArray(int[] nums) {
        // If any number is 1, the GCD of the whole array will be 1.
        for (int num : nums) {
            if (num == 1) return true;
        }

        Set<Integer> commonFactors = getPrimeFactors(nums[0]);
        if (commonFactors.isEmpty()) {
            return true; 
        }

        for (int i = 1; i < nums.length; i++) {
            Set<Integer> nextCommonFactors = new HashSet<>();
            for (int factor : commonFactors) {
                if (nums[i] % factor == 0) {
                    nextCommonFactors.add(factor);
                }
            }
            commonFactors = nextCommonFactors;
            if (commonFactors.isEmpty()) {
                return true;
            }
        }

        return commonFactors.isEmpty();
    }
}
```
### Algorithm
- The problem is equivalent to checking if the GCD of all elements in `nums` is 1, based on Bézout's identity.
- Find all distinct prime factors of the first element, `nums[0]`, and store them in a set.
- Iterate through the rest of the array elements.
- For each element, filter the set of common prime factors, keeping only those that also divide the current element.
- If the set of common prime factors becomes empty at any point, it means the GCD of the prefix of the array processed so far is 1. The final GCD will also be 1, so we can return `true` immediately.
- If the loop completes and the set of common factors is not empty, the GCD of the entire array is greater than 1. Return `false`.

## Iterative GCD with Euclidean Algorithm
This is the optimal approach, which also relies on Bézout's identity. It simplifies the problem to checking if the greatest common divisor (GCD) of all elements in the `nums` array is 1. The GCD is calculated efficiently by iterating through the array and repeatedly applying the Euclidean algorithm.
**Time:** O(N * log(M)), where N is the number of elements in the array and M is the maximum value of an element in `nums`. The Euclidean algorithm `gcd(a, b)` takes `O(log(min(a, b)))` time. · **Space:** O(1), as the computation is done in-place with a few variables.
**Pros:** Highly efficient and optimal solution.; Simple and concise implementation.; Directly uses a standard, fast algorithm for GCD computation.
**Cons:** The connection to the problem statement requires understanding Bézout's identity, which might not be immediately obvious.
### Explanation
The problem is a direct application of a mathematical theorem known as Bézout's identity. The theorem states that for any set of integers `a_1, ..., a_k`, an equation of the form `c_1*a_1 + ... + c_k*a_k = d` has integer solutions for `c_i` if and only if `d` is a multiple of the greatest common divisor (GCD) of `a_1, ..., a_k`.

In our case, we want the sum to be 1. This is possible if and only if we can find a subset of `nums` whose GCD is 1. If the GCD of the entire array `nums` is `g > 1`, then any linear combination of any subset of `nums` will be a multiple of `g`, and can never equal 1. Therefore, the problem simplifies to checking if the GCD of all elements in `nums` is 1.

This approach calculates the GCD of the entire array efficiently by iteratively applying the Euclidean algorithm.

```java
class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public boolean isGoodArray(int[] nums) {
        if (nums.length == 0) {
            return false;
        }
        
        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;
    }
}
```
### Algorithm
- The problem is equivalent to checking if `gcd(nums[0], nums[1], ..., nums[n-1]) == 1` due to Bézout's identity.
- Initialize a result variable `currentGcd` with the first element `nums[0]`.
- Iterate through the array from the second element `nums[1]`.
- In each step, update `currentGcd = gcd(currentGcd, nums[i])`, where `gcd` is the Euclidean algorithm for finding the greatest common divisor.
- If `currentGcd` becomes 1 at any point, we can stop and return `true` since the final GCD is guaranteed to be 1.
- After iterating through the entire array, if `currentGcd` is 1, return `true`. Otherwise, return `false`.

# Solutions
### Java

```java
class Solution { public boolean isGoodArray ( int [] nums ) { int g = 0 ; for ( int x : nums ) { g = gcd ( x , g ); } return g == 1 ; } private int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } }
```

### CPP

```cpp
class Solution { public: bool isGoodArray ( vector < int >& nums ) { int g = 0 ; for ( int x : nums ) { g = gcd ( x , g ); } return g == 1 ; } };
```

### Python

```python
class Solution : def isGoodArray ( self , nums : List [ int ]) -> bool : return reduce ( gcd , nums ) == 1
```