Check If It Is a Good Array
Problem
Given an array nums of positive integers, you can pick any subset of it and multiply each chosen number by any integer (positive, negative, or zero), then sum the products. The array is good if some such combination sums to exactly 1. Return whether nums is good.
By Bézout's identity, integer multipliers producing a sum of 1 exist if and only if the greatest common divisor (GCD) of all the numbers equals 1.
nums = [12, 5, 7, 23]truefrom math import gcd
from functools import reduce
def is_good_array(nums):
g = reduce(gcd, nums)
return g == 1function gcd(a, b) {
while (b) { [a, b] = [b, a % b]; }
return a;
}
function isGoodArray(nums) {
let g = nums[0];
for (let i = 1; i < nums.length; i++) g = gcd(g, nums[i]);
return g === 1;
}class Solution {
int gcd(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
public boolean isGoodArray(int[] nums) {
int g = nums[0];
for (int i = 1; i < nums.length; i++) g = gcd(g, nums[i]);
return g == 1;
}
}int gcd(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
bool isGoodArray(vector<int>& nums) {
int g = nums[0];
for (int i = 1; i < (int)nums.size(); i++) g = gcd(g, nums[i]);
return g == 1;
}Explanation
The question asks whether we can mix the numbers with integer multipliers to reach a total of exactly 1. The whole answer boils down to one check: is the GCD of all the numbers equal to 1?
This comes from Bézout's identity: an integer combination of the numbers can equal any multiple of their greatest common divisor, and nothing smaller. So a combination can hit 1 exactly when the GCD is 1.
The code keeps a running value g, starting at the first number, and folds every other number in with g = gcd(g, nums[i]). At the end it returns whether g == 1.
The gcd helper uses the classic Euclidean trick: repeatedly replace (a, b) with (b, a % b) until b becomes 0, leaving the GCD in a.
Example: nums = [12, 5, 7, 23]. Running GCD goes 12 → gcd(12,5)=1, and once it hits 1 it stays 1. So the final g is 1 and the array is good (true).