Check If It Is a Good Array Solved (Explanation)- beats 100%(Java,c#,c++,JS,TypeScript,Python)
Intuition
The problem requires us to determine if we can generate the number 1 by taking a subset of the numbers in the array and multiplying them by integers.
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- The problem requires us to determine if we can generate the number 1 by taking a subset of the numbers in the array and multiplying them by integers.
- This boils down to finding if the greatest common divisor (GCD) of all the numbers in the array is 1, because if the GCD of all the numbers is 1, then we can find integer multiples that sum to 1.
- If the GCD is greater than 1, it's impossible to make 1, because all multiples of any number that shares a GCD greater than 1 will be divisible by that GCD.
# Approach
<!-- Describe your approach to solving the problem. -->
- Initialize the gcd with the first number in the array.
- Traverse the array, updating the gcd with each number using the Euclidean algorithm.
- If at any point, the gcd becomes 1, we can immediately return true since we know it's possible to form 1 from the array.
- If after iterating through all the numbers the GCD is still greater than 1, return false.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n * log(max(nums)))$$, where n is the length of the array, and max(nums) is the largest number. The gcd() function takes logarithmic time relative to the smaller of the two numbers.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(1)$$, because we're using a constant amount of extra space

# Code
```java []
//Not Recomended
<!-- class Solution {
    public boolean isGoodArray(int[] nums) {

        int x =nums[0],y;
        for(int a: nums){
            while( a> 0){
                y=x%a;
                x=a;
                a=y;
            }
        }
        return x ==1;
        
    }
} -->
 class Solution {
     public boolean isGoodArray(int[] nums) {
         int gcd = nums[0];
        
         for (int i = 1; i < nums.length; i++) {
             gcd = gcd(gcd, nums[i]);
             if (gcd == 1) {
                 return true; // Early exit if GCD becomes 1
             }
         }
        
         return gcd == 1;
     }
    
     // Helper function to compute GCD of two numbers using Euclidean algorithm
     private int gcd(int a, int b) {
         while (b != 0) {
             int temp = b;
             b = a % b;
             a = temp;
         }
         return a;
     }
 }
```
```C# []
// C# Solution
public class Solution {
    public bool IsGoodArray(int[] nums) {
        int gcd = nums[0];
        
        for (int i = 1; i < nums.Length; i++) {
            gcd = Gcd(gcd, nums[i]);
            if (gcd == 1) {
                return true; // Early exit if GCD becomes 1
            }
        }
        
        return gcd == 1;
    }
    
    // Helper function to compute GCD of two numbers using Euclidean algorithm
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

```
```Python []
# Python Solution
from math import gcd
from functools import reduce

def isGoodArray(nums):
    gcd_value = nums[0]
    
    for num in nums[1:]:
        gcd_value = gcd(gcd_value, num)
        if gcd_value == 1:
            return True # Early exit if GCD becomes 1
    
    return gcd_value == 1

```
```JS []
// JavaScript Solution
var isGoodArray = function(nums) {
    let gcd = nums[0];

    for (let i = 1; i < nums.length; i++) {
        gcd = getGCD(gcd, nums[i]);
        if (gcd === 1) {
            return true; // Early exit if GCD becomes 1
        }
    }

    return gcd === 1;
};

// Helper function to compute GCD of two numbers using Euclidean algorithm
function getGCD(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

```
```C++ []
// C++ Solution
class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int gcd_value = nums[0];
        
        for (int i = 1; i < nums.size(); i++) {
            gcd_value = gcd(gcd_value, nums[i]);
            if (gcd_value == 1) {
                return true; // Early exit if GCD becomes 1
            }
        }
        
        return gcd_value == 1;
    }

    // Helper function to compute GCD of two numbers using Euclidean algorithm
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};

```
```TypeScript []
// TypeScript Solution
function isGoodArray(nums: number[]): boolean {
    let gcd_value = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        gcd_value = getGCD(gcd_value, nums[i]);
        if (gcd_value === 1) {
            return true; // Early exit if GCD becomes 1
        }
    }
    
    return gcd_value === 1;
}

// Helper function to compute GCD of two numbers using Euclidean algorithm
function getGCD(a: number, b: number): number {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

```
['Array', 'Python', 'C++', 'Java', 'TypeScript', 'JavaScript', 'C#']