Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1250.html
1250. Check If It Is a Good Array
Level
Hard
Description
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.
53 + 7(-2) = 1
Example 2:
Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
291 + 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
This problem is actually a number theory problem. Although marked as Hard difficulty, this problem can be easily solved once the number theory knowledge behind is applied.
For any two positive integers x and y, there exist two integers a and b such that ax+by=1 if and only if the greatest common divisor of a and b is 1.
Therefore, just calculate the greatest common divisor of all the numbers in the given array num. If at one step, the greatest common divisor become 1, then stop calculating further since the greatest common divisor of 1 and any positive integer is 1.
If the greatest common divisor is 1, return True. Otherwise, return False.
-
class Solution { public boolean isGoodArray(int[] nums) { int length = nums.length; int gcd = nums[0]; for (int i = 1; i < length; i++) { gcd = gcd(gcd, nums[i]); if (gcd == 1) return true; } return gcd == 1; } public int gcd(int num1, int num2) { if (num1 == 0 && num2 == 0) return 1; if (num1 == 1 || num2 == 1) return 1; if (num1 > num2) { int temp = num1; num1 = num2; num2 = temp; } while (num1 != 0 && num2 != 0) { num2 %= num1; int temp = num1; num1 = num2; num2 = temp; } if (num1 == 0) return num2; else return num1; } } -
// OJ: https://leetcode.com/problems/check-if-it-is-a-good-array/ // Time: O(N) // Space: O(1) class Solution { public: bool isGoodArray(vector<int>& A) { int d = A[0]; for (int i = 1; i < A.size(); ++i) { d = gcd(d, A[i]); } return d == 1; } }; -
class Solution: def isGoodArray(self, nums: List[int]) -> bool: return reduce(gcd, nums) == 1 -
func isGoodArray(nums []int) bool { g := 0 for _, x := range nums { g = gcd(x, g) } return g == 1 } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }