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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        n = nums[0]
        
        for i in nums:
            n = gcd(i,n)
            
            if n==1:
                return True
        return False


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        if not nums: return False
        a=nums[0]
        for i in range(1, len(nums)):
            a=gcd(a,nums[i])
        return a==1

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(x,y):
            while y:
                x,y=y,x%y
            return x
        g=nums[0]
        for x in nums:
            g=gcd(g,x)
        return g==1


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(x: int, y: int) -> int:
            if y == 0:
                return x
            else:
                return gcd(y, x % y)
            
        result = nums[0]
        for num in nums:
            result = gcd(result, num)
            
        return result == 1

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        gcd = nums[0]
        for a in nums:
            while a:
                gcd, a = a, gcd % a
        return gcd == 1


class Solution:
    def gcd(self,a,b):
        return a if b==0 else self.gcd(b,a%b)
    def isGoodArray(self, nums: List[int]) -> bool:
        nums=list(set(nums))
        n=len(nums)
        if n==1 and nums[0]==1:return True
        cur=nums[0]        
        for i in range(1,n):
            cur=self.gcd(cur,nums[i])
            if cur==1:return True
        return False

class Solution:
    def gcd(self, a, b):
        if a == 0:
            return b
        if b == 0:
            return a
        if a == 1 or b == 1:
            return 1
        while b != 0:
            a, b = b, a % b
        return a
    
    def isGoodArray(self, nums: List[int]) -> bool:
        g = 0
        for n in nums:
            if g == 0:
                g = n
            elif n == 1:
                return True
            else:
                while n:
                    g, n = n, g % n
            if g == 1:
                return True
        return False

class Solution:
    
    def gcd(self, a:int, b:int) -> int:
        a,b = max(a,b),min(a,b)
        while b>0:
            a,b = b,a%b
        return a
    
    def isGoodArray(self, nums: List[int]) -> bool:
        lowest = nums[0]
        for i in nums[1:]:
            lowest = self.gcd(lowest,i)
        return lowest==1

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return nums[0] == 1
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        gcd_val = nums[0]
        for i in range(1, len(nums)):
            gcd_val = gcd(gcd_val, nums[i])
            if gcd_val == 1:
                return True
        return False

def gcd(a,b):
    if(b==0):
        return a
    return gcd(b,a%b)

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        if(nums==[1]):
            return True
        i=0
        a=nums[i]
        for j in range(i+1,len(nums)):
            if(a<nums[j]):
                b=gcd(nums[j],a)
                if(b==1):
                    return True
                else:
                    a=b
            else:
                b=(gcd(a,nums[j]))
                if(b==1):
                    return True
                else:
                    a=b
        return False

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        gcd = nums[0]
        for n in nums:
            while n:
                gcd, n = n, gcd % n
        return gcd == 1
            


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(a, b):
            a, b = max(a,b), min(a,b)
            while b:
                a, b = b, a%b
            return a
        if len(nums) == 1:
            if nums != [1]:
                return False
            else:
                return True
        i = 0
        d = nums[0]
        while i < len(nums):
            d = gcd(nums[i],d)
            if d == 1:
                return True
            i += 1
        return False


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        
        def gcd(x, y):
            if x < y:
                x, y = y, x
            if not x % y:
                return y
            return gcd(x % y, y)
        
        if len(nums) == 1:
            if nums[0] == 1:
                return True
            return False
        
        while True:
            x = nums.pop(-1)
            y = nums.pop(-1)
            z = gcd(x, y)
            if not nums:
                return z == 1
            
            nums.append(z)


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        
        def euclid(a,b):
            q, r = max(a,b), min(a,b)
            while r > 1 and q > 0:
                r, q = q % r, r
            return r if r > 0 else q
            
        if len(nums) == 1:
            return True if nums[0] == 1 else False
        
        nums.sort()
        for i in range(1,len(nums)):
            nums[i] = euclid(nums[i],nums[i-1])
            if nums[i] == 1:
                return True
            
        return False

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def euclid(a,b):
            q, r = max(a,b), min(a,b)
            while r > 1 and q > 0:
                r, q = q % r, r
            return r if r > 0 else q
            
        if len(nums) == 1:
            return True if nums[0] == 1 else False
        
        for i in range(1,len(nums)):
            nums[i] = euclid(nums[i],nums[i-1])
            if nums[i] == 1:
                return True
            
        return False

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(a, b):
            if b>0:
                return gcd(b, a%b)
            return a
        if not nums:
            return False
        if len(nums)==1:
            return nums[0]==1
        num = nums[0]
        for i in range(1, len(nums)):
            ans = gcd(num, nums[i])
            if ans==1:
                return True
            num = ans
        return False


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            if nums[0] == 1:
                return True
            else:
                return False
    
        ans = self.gcd(nums[0],nums[1])
        for num in nums[2:]:
            ans = self.gcd(ans,num)
            if ans == 1:
                return True
        return ans == 1
    def gcd(self, a,b) :
        if b == 0:
            return a
        return self.gcd(b,a%b)


from math import gcd
from functools import reduce

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        return (reduce((lambda x, y: gcd(x,y)), nums) == 1)
    
# class Solution:
#     def gcd(x, y):
#         gcd_ = i
#         for i in range(2, min(x, y)):
#             if x%i == 0 and y%i == 0:
#                 gcd_ = i
#         return gcd_
#     def isGoodArray(self, nums: List[int]) -> bool:
#         itergcd = nums[0]
#         for i in nums:
#             itergcd = gcd(itergcd, i)
#         return itergcd == 1
            


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        import math
        curr_gcd = nums[0]
        for i in range(1, len(nums)):
            curr_gcd = math.gcd(curr_gcd, nums[i])
            if curr_gcd == 1:
                return True
        return curr_gcd == 1
        
        # if 1 in nums: return True
        
#         def find_factors(num):
#             sol = set()
#             for i in range(1,math.ceil(math.sqrt(num))):
#                 if num % i == 0:
#                     sol.add(i)
#                     sol.add(num/i)
#             # sol.remove(num)
#             sol.remove(1)
#             return sol
        
#         all_items = set()
#         factors_list = []
#         for num in nums:
#             temp_set = find_factors(num)
#             for it in temp_set:
#                 all_items.add(it)
            
#             factors_list.append(temp_set)
#         # print(all_items)
#         # print(factors_list)        
#         for it in all_items:
#             if it == 1: continue
#             if all([it in lis for lis in factors_list]):
#                 return False

#         return True
        
        
        
        
        '''
        29, 6, 10
        29, 3*2, 5*2
        '''

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            nums[i] = gcd(nums[i],nums[i-1]) if i > 0 else nums[0]
        
        return nums[-1]==1
    


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(x,y):
            if y > x:
                return gcd(y,x)
            if y == 0:
                return x
            return gcd(y,x%y) 
        cur = nums[0]
        for i in range(1, len(nums)):
            cur = gcd(cur,nums[i])
        
        return cur == 1


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        g=nums[0]
        for i in nums:g=gcd(i,g)
        return g==1

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        gcd = nums[0]
        for num in nums:
            while num:
                gcd, num = num, gcd % num
            if gcd == 1:
                return True
        return False


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        
        def gcd(a,b):
            if b > a:
                a,b = b,a
            while (b > 0):
                r = divmod(a,b)[1]
                a = b
                b = r
            return a
        
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0] == 1
        
        ans = nums[0]
        
        for i in range(1,len(nums)):
            ans = gcd(ans,nums[i])
            if ans == 1: return True
        
        return ans == 1

class Solution:
    def gcd(self, nums):
        g = nums[0]
        for x in nums:
            while x:
                g, x = x, g%x
        return g

    # a: list of integers
    # d: desired GCD of the integers in a
    def bezout(self, a: [int], d):
        if self.gcd(a) == d:
            return True
        return False

    def isGoodArray(self, nums: [int]) -> bool:
        return self.bezout(nums, 1)

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        gcd = nums[0]
        for n in nums:
            while n:
                gcd, n = n, gcd % n
                
        return gcd == 1

class Solution:
  def getGCD(self, x: int, y: int) -> int:
    while y:
      x, y = y, x % y
    return x  
  def getLCM(self, x: int, y: int) -> int:
    return x * y // self.getGCD(x, y)
  def isGoodArray(self, nums: List[int]) -> bool:
    # question is equivalent to have any substr with gcd equals 1, iff array has gcd equals to 1
    n = len(nums)
    x, i = nums[0], 1
    while i < n:
      x = self.getGCD(x, nums[i])
      if x == 1:
        return True
      i += 1
    return x == 1

class Solution:
    def isGoodArray(self, A: List[int]) -> bool:
        gcd = A[0]
        for a in A:
            while a:
                gcd, a = a, gcd % a
                if gcd == 1:
                    return gcd
        return False

from fractions import gcd
from functools import reduce
class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def find_gcd(list):
            x = reduce(gcd, list)
            return x
        if find_gcd(nums)==1:
            return True
        return False



# from math import gcd
# from functools import reduce

# class Solution:
#     def isGoodArray(self, nums: List[int]) -> bool:
#         return (reduce((lambda x, y: gcd(x,y)), nums) == 1)
    
class Solution:
    def gcd(x, y):
        gcd_ = i
        for i in range(2, min(x, y)):
            if x%i == 0 and y%i == 0:
                gcd_ = i
        return gcd_
    def isGoodArray(self, nums: List[int]) -> bool:
        start = nums[0]
        for i in nums:
            start = gcd(start, i)
        return start == 1
            


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        g=nums[0]
        for i in nums:
            g=self.hcfnaive(i,g)
        return g==1
            
      
    def hcfnaive(self,a,b): 
        if(b==0): 
            return a 
        else: 
            return self.hcfnaive(b,a%b) 


class Solution:
    def isGoodArray(self, x: List[int]) -> bool:
        g=x[0]
        for i in x:g=gcd(i,g)
        return g==1


from functools import reduce
class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        return reduce(gcd, nums) < 2
            


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        
        if len(nums) == 1:
            if nums[0] == 1:
                return True
            else:
                return False
            
        now = -1
        for i in range(1, len(nums)):
            if i == 1:
                now = math.gcd(nums[i-1], nums[i])
            else:
                now = math.gcd(nums[i],now)
            
        
        if now == 1:
            return True
        return False

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        res = nums[0]
        
        for i in range(1, len(nums)):
            res = math.gcd(res, nums[i])
            if res == 1:
                return True
        
        return res == 1


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        
        if len(nums) == 1:
            return True if nums[0] == 1 else False
    
        for i in range(1,len(nums)):
            nums[i] = gcd(nums[i],nums[i-1])
            if nums[i] == 1:
                return True
            
        return False
    


class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
#         primeSet = set()
#         def isPrime(x):
#             if x < 2 or x in primeSet:
#                 return False
#             i = 2
#             limit = int(x**0.5)
#             while i < limit +1:
#                 if x%i == 0:
#                     return False
#                 limit = x//i
#                 i += 1
#             primeSet.add(x)
#             return True
        
#         numsLen = len(nums)
#         primeCounter = 0
#         for i in range(numsLen):
#             if nums[i] == 1:
#                 return True
#             if isPrime(nums[i]):
#                 primeCounter += 1
#                 if primeCounter == 2:
#                     return True
#             else:
#                 for j in range(i):
#                     if isPrime(abs(nums[j] - nums[i])):
#                         primeCounter += 1
#                         if primeCounter == 2:
#                             return True
#         return False
        g=nums[0]
        for i in nums:
            g=gcd(i,g)
        return g==1

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            nums[i] = gcd(nums[i],nums[i-1]) if i > 0 else nums[0]
            if nums[i] == 1:
                return True
        return False
    


class Solution:
    def isGoodArray(self, A: List[int]) -> bool:
        if len(A) == 0:
            return False
        gcd = A[0]
        for a in A:
            while a:
                gcd, a = a, gcd % a
        return gcd == 1