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
SOLUTION:
class Solution:
def gcd(self, a, b):
while b:
a, b = b, a % b
return a
def isGoodArray(self, nums: List[int]) -> bool:
n = len(nums)
curr = nums[0]
for i in range(1, n):
curr = self.gcd(curr, nums[i])
if curr == 1:
return True
return curr == 1
# class Solution:
# def gcd(self, a, b):
# while b:
# a, b = b, a % b
# return a
# def isGoodArray(self, nums: List[int]) -> bool:
# n = len(nums)
# paths = [([i], nums[i]) for i in range(n)]
# i = 0
# while i < len(paths):
# curr, currgcd = paths[i]
# if currgcd == 1:
# return True
# for j in range(curr[-1] + 1, n):
# paths.append((curr + [j], self.gcd(currgcd, nums[j])))
# i += 1
# return False
Top comments (0)