## DEV Community

Abhishek Chaudhary

Posted on

# Check If It Is a Good Array

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