Problem

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.

Examples

Example 1

1
2
3
4

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2

1
2
3
4

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3

1
2

Input: nums = [3,6]
Output: false

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – GCD and Bézout’s Identity

Intuition

The array is good if we can form 1 as a linear combination of the numbers with integer coefficients. By Bézout’s identity, this is possible if and only if the greatest common divisor (GCD) of the array is 1.

Approach

  1. Compute the GCD of all elements in the array.
  2. If the GCD is 1, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int g = nums[0];
        for (int x : nums) g = gcd(g, x);
        return g == 1;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func isGoodArray(nums []int) bool {
    g := nums[0]
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range nums {
        g = gcd(g, x)
    }
    return g == 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public boolean isGoodArray(int[] nums) {
        int g = nums[0];
        for (int x : nums) g = gcd(g, x);
        return g == 1;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun isGoodArray(nums: IntArray): Boolean {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        var g = nums[0]
        for (x in nums) g = gcd(g, x)
        return g == 1
    }
}
1
2
3
4
5
6
7

class Solution:
    def isGoodArray(self, nums: list[int]) -> bool:
        from math import gcd
        g = nums[0]
        for x in nums:
            g = gcd(g, x)
        return g == 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn is_good_array(nums: Vec<i32>) -> bool {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        let mut g = nums[0];
        for &x in &nums {
            g = gcd(g, x);
        }
        g == 1
    }
}

Complexity

  • ⏰ Time complexity: O(N log M), where N is the length of the array and M is the maximum value in nums.
  • 🧺 Space complexity: O(1)