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

Source: leetcode | Difficulty: MEDIUM
Tags: Number theory

Data structures

Mathematics

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


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 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 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


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

	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 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:
		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


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)


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