1250. Check If It Is a Good Array

Problem Description

The problem presents us with an array of positive integers called nums. Our goal is to check if it's possible to select a subset of these numbers, multiply each selected number by an integer, and then sum them up to get a total of 1. If this is possible, the array is considered "good". Otherwise, it is not good. The task is to determine if the given array is good or not, and we are to return True if it is good and False if it is not.

Intuition

To determine if an array is good or not, we can use a mathematical concept called the Greatest Common Divisor (GCD). The GCD of two numbers is the largest number that divides both of them without leaving a remainder. If we can extend this concept to find the GCD of all numbers in the array and the result is 1, this implies that we can form the number 1 as a linear combination of the array numbers, using the Bezout's identity theorem.

This means that if the GCD of the entire array is 1, there must be some subset of numbers in the array which can be multiplied by some integers to sum up to 1, since 1 is the only number that when used in linear combinations can produce any integer (and specifically the integer 1 in our case).

The Python code makes use of the reduce function and the gcd function from the [math](/problems/math-basics) module. The reduce function is used to apply the gcd function cumulatively to the items of nums, from left to right, so that we are effectively finding the GCD of all the numbers in the array. If the GCD turns out to be 1, the function returns True. Otherwise, it returns False. This simple approach elegantly checks if the array is good using built-in functions to perform the necessary calculations.

Learn more about Math patterns.

Solution Approach

The solution to this problem leverages the mathematical property of the Greatest Common Divisor (GCD) and a functional programming construct in Python.

Here's the step-by-step breakdown of the implementation:

• Step 1: Import the gcd function from the [math](/problems/math-basics) module. gcd takes two numbers as arguments and returns their greatest common divisor.

• Step 2: Use the reduce function from the functools module. The reduce function is a tool for performing a cumulative operation over an iterable. In this case, it applies the gcd function starting with the first two elements of the nums array, and then consecutively using the result as the first argument and the next element in the array as the second argument.

• Step 3: The reduce function will apply the gcd function progressively across all elements of the array. Essentially, this means it will calculate the gcd of the first and second elements, then take that result and calculate the gcd with the third element, and so on until it processes the entire array.

• Step 4: After reduce has processed all the elements, we evaluate whether the accumulated GCD is 1. If the result is 1, it signifies that there is some combination of the array elements along with respective multiplicands that could add up to 1 (thanks to Bezout's identity). If not, it implies that no such combination is possible.

• Step 5: The isGoodArray method returns True if the GCD is 1, signaling that the array is “good”, or returns False otherwise.

The algorithm relies on the following data structures and patterns:

• Arrays: The given input is an array that the algorithm iterates through.
• Functional Programming: Using reduce is an example of functional programming, as it applies a function cumulatively to the items of an iterable in a non-mutable way.

And that's it. By efficiently applying the gcd function cumulatively across all elements in the nums array, we can ascertain whether the array is "good" with a single line of code after the necessary functions are imported:

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

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we are given the following array of positive integers:

1nums = [6, 10, 15]

Now, let's walk through the process step by step:

• Step 1: We first import the gcd function from the math module, which will allow us to calculate the greatest common divisor of two given numbers.

• Step 2: We use the reduce function from the functools module to apply the gcd function cumulatively to the numbers in our array nums.

• Step 3: First, reduce applies the gcd function to the first two elements, which are 6 and 10. The gcd of 6 and 10 is 2.

• Step 4: The result (2) is then used with the next element in the array, which is 15. The gcd of 2 and 15 is 1.

• Step 5: Since the reduce function has finished processing all elements, we check if the accumulated GCD is 1. In our case, it is indeed 1.

According to Bezout's identity, because the final GCD is 1, there must be a combination of integer multiples of some or all numbers in our array nums that can add up to 1. Hence, for our input array, the function isGoodArray would evaluate to True, indicating that the array is "good".

Here's a glimpse of how the code operates in this scenario:

1from functools import reduce
2from math import gcd
3
4nums = [6, 10, 15]
5result = reduce(gcd, nums)
6is_good = result == 1  # This would be True in this case

The simplicity of this algorithm lies in its use of the gcd function to examine the entire array in a single sweep. If the gcd of all elements is 1, we can confidently say that the array is "good" as it meets the criteria outlined in the problem description.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by the reduce function and the gcd (greatest common divisor) operations it performs on the list elements.

• The reduce function applies the gcd function cumulatively to the items of the list, from start to end, to reduce the list to a single value.
• The gcd function runs in O(log(min(a, b))) time, where a and b are the numbers whose GCD is being calculated.

Assuming there are n elements in the nums list, the reduce function will perform n-1 gcd operations. Due to the nature of GCD calculation, where after the first operation, the resulting GCD will often be lesser than or equal to the smallest number among the operands, each subsequent gcd operation is typically faster than the last. However, for worst-case analysis, we'll consider each operation to have the complexity of O(log(k)), where k is the smallest element after each operation.

Therefore, the time complexity is:

1O(n*log(k))

Where n is the number of elements in the list and k is the smallest number in the list at each step of the reduction.

Space Complexity

The space complexity of the code is O(1).

• This space complexity comes from the fact that the gcd operations do not require additional space that scales with the input size, as they are computed in constant space.
• The reduce function does not create any new data structures that depend on the input size; it just iterates over the existing list and updates the accumulator in-place.

Thus, the space complexity is:

1O(1)

Learn more about how to find time and space complexity quickly using problem constraints.