Check If It Is a Good Array

Hard

#1167Time: O(sqrt(M) + N * k), where N is the number of elements in the array, M is the value of the first element `nums[0]`, and k is the number of distinct prime factors of `nums[0]`. This is generally slower than the Euclidean algorithm approach.Space: O(k), where k is the number of distinct prime factors of `nums[0]`. This space is used to store the common prime factors.3 companies

Patterns

Math Number Theory

Data structures

Array

Companies

Dropbox Nokia Jump Trading

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach determines if the array is 'good' by calculating the greatest common divisor (GCD) of all its elements using prime factorization. Based on Bézout's identity, a linear combination of numbers can sum to 1 if and only if their GCD is 1. The array is good if the GCD of all its elements is 1. This method finds common prime factors among all numbers to compute their GCD.

Algorithm

The problem is equivalent to checking if the GCD of all elements in nums is 1, based on Bézout's identity.
Find all distinct prime factors of the first element, nums[0], and store them in a set.
Iterate through the rest of the array elements.
For each element, filter the set of common prime factors, keeping only those that also divide the current element.
If the set of common prime factors becomes empty at any point, it means the GCD of the prefix of the array processed so far is 1. The final GCD will also be 1, so we can return true immediately.
If the loop completes and the set of common factors is not empty, the GCD of the entire array is greater than 1. Return false.

Walkthrough

The problem asks if we can find a subset of nums and integer multipliers to form a sum of 1. This is a classic problem related to Bézout's identity, which states that an integer linear combination of numbers a_1, a_2, ..., a_k can equal their greatest common divisor (GCD). To get a sum of 1, the GCD of the chosen subset must be 1. A key property is that for any subset S of nums, gcd(S) must be a multiple of gcd(nums). Therefore, if we can find a subset with GCD 1, the GCD of the entire array must also be 1. Conversely, if gcd(nums) = 1, we can simply choose the whole array as our subset. The problem thus reduces to checking if gcd(nums) == 1.

This approach computes the GCD by finding common prime factors. It's less efficient but demonstrates the concept from first principles. The algorithm finds the prime factors of the first number and then iteratively filters this set by checking divisibility against subsequent numbers. If the set of common prime factors becomes empty, the GCD is 1.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    private Set<Integer> getPrimeFactors(int n) {6        Set<Integer> factors = new HashSet<>();7        if (n == 1) return factors;8        for (int i = 2; i * i <= n; i++) {9            if (n % i == 0) {10                factors.add(i);11                while (n % i == 0) {12                    n /= i;13                }14            }15        }16        if (n > 1) {17            factors.add(n);18        }19        return factors;20    }21 22    public boolean isGoodArray(int[] nums) {23        // If any number is 1, the GCD of the whole array will be 1.24        for (int num : nums) {25            if (num == 1) return true;26        }27 28        Set<Integer> commonFactors = getPrimeFactors(nums[0]);29        if (commonFactors.isEmpty()) {30            return true; 31        }32 33        for (int i = 1; i < nums.length; i++) {34            Set<Integer> nextCommonFactors = new HashSet<>();35            for (int factor : commonFactors) {36                if (nums[i] % factor == 0) {37                    nextCommonFactors.add(factor);38                }39            }40            commonFactors = nextCommonFactors;41            if (commonFactors.isEmpty()) {42                return true;43            }44        }45 46        return commonFactors.isEmpty();47    }48}

Complexity

Time

O(sqrt(M) + N * k), where N is the number of elements in the array, M is the value of the first element `nums[0]`, and k is the number of distinct prime factors of `nums[0]`. This is generally slower than the Euclidean algorithm approach.

Space

O(k), where k is the number of distinct prime factors of `nums[0]`. This space is used to store the common prime factors.

Trade-offs

Pros

Provides a solution based on the fundamental theorem of arithmetic, illustrating the concept of GCD through prime factors.

Cons

Significantly less efficient than using the Euclidean algorithm, especially for large numbers.
Prime factorization is computationally expensive.
The implementation is more complex.

This is the optimal approach, which also relies on Bézout's identity. It simplifies the problem to checking if the greatest common divisor (GCD) of all elements in the nums array is 1. The GCD is calculated efficiently by iterating through the array and repeatedly applying the Euclidean algorithm.

Algorithm

The problem is equivalent to checking if gcd(nums[0], nums[1], ..., nums[n-1]) == 1 due to Bézout's identity.
Initialize a result variable currentGcd with the first element nums[0].
Iterate through the array from the second element nums[1].
In each step, update currentGcd = gcd(currentGcd, nums[i]), where gcd is the Euclidean algorithm for finding the greatest common divisor.
If currentGcd becomes 1 at any point, we can stop and return true since the final GCD is guaranteed to be 1.
After iterating through the entire array, if currentGcd is 1, return true. Otherwise, return false.

Walkthrough

The problem is a direct application of a mathematical theorem known as Bézout's identity. The theorem states that for any set of integers a_1, ..., a_k, an equation of the form c_1*a_1 + ... + c_k*a_k = d has integer solutions for c_i if and only if d is a multiple of the greatest common divisor (GCD) of a_1, ..., a_k.

In our case, we want the sum to be 1. This is possible if and only if we can find a subset of nums whose GCD is 1. If the GCD of the entire array nums is g > 1, then any linear combination of any subset of nums will be a multiple of g, and can never equal 1. Therefore, the problem simplifies to checking if the GCD of all elements in nums is 1.

This approach calculates the GCD of the entire array efficiently by iteratively applying the Euclidean algorithm.

1class Solution {2    private int gcd(int a, int b) {3        while (b != 0) {4            int temp = b;5            b = a % b;6            a = temp;7        }8        return a;9    }10 11    public boolean isGoodArray(int[] nums) {12        if (nums.length == 0) {13            return false;14        }15        16        int currentGcd = nums[0];17        18        for (int i = 1; i < nums.length; i++) {19            currentGcd = gcd(currentGcd, nums[i]);20            if (currentGcd == 1) {21                return true;22            }23        }24        25        return currentGcd == 1;26    }27}

Complexity

Time

O(N * log(M)), where N is the number of elements in the array and M is the maximum value of an element in `nums`. The Euclidean algorithm `gcd(a, b)` takes `O(log(min(a, b)))` time.

Space

O(1), as the computation is done in-place with a few variables.

Trade-offs

Pros

Highly efficient and optimal solution.
Simple and concise implementation.
Directly uses a standard, fast algorithm for GCD computation.

Cons

The connection to the problem statement requires understanding Bézout's identity, which might not be immediately obvious.

Solutions

Solution

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

1class Solution { public: bool isGoodArray ( vector < int >& nums ) { int g = 0 ; for ( int x : nums ) { g = gcd ( x , g ); } return g == 1 ; } };

1class Solution : def isGoodArray ( self , nums : List [ int ]) -> bool : return reduce ( gcd , nums ) == 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem