We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If It Is a Good Array

Number: 1372

Difficulty: Hard

Paid? No

Companies: Bloomberg, Amazon, Dropbox

Problem Description

Given an array nums of positive integers, determine if it is possible to select some subset of nums and multiply each selected element by an integer such that their sum equals 1. The array is considered "good" if there exists any combination where the sum becomes 1.

Key Insights

  • The problem can be reduced to calculating the greatest common divisor (GCD) of all numbers in the array.
  • According to Bezout's Identity, if the GCD of the array is 1, then there exist integer coefficients that can form a linear combination equal to 1.
  • If the GCD is greater than 1, it is impossible to form a sum of 1.
  • An iterative GCD computation can be used to determine the answer efficiently.

Space and Time Complexity

Time Complexity: O(n * log(max(nums))) where n is the number of elements and log(max(nums)) is due to the GCD computation. Space Complexity: O(1) since only a fixed number of extra variables are used.

Solution

We solve the problem by iteratively computing the GCD of the array elements using the Euclidean algorithm. Begin with the first element as the initial GCD and update it with each subsequent element. If at any point the GCD becomes 1, we can return True early. Finally, if the overall GCD is 1, the array is considered good, otherwise it is not.

Code Solutions

def isGoodArray(nums):
    # Helper function to compute the GCD using the Euclidean algorithm
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    # Initialize the current GCD with the first element of the array
    current_gcd = nums[0]
    for num in nums[1:]:
        # Update the current_gcd with the GCD of current_gcd and the next number
        current_gcd = gcd(current_gcd, num)
        # Early return if we find a GCD of 1
        if current_gcd == 1:
            return True
    return current_gcd == 1

# Example usage:
print(isGoodArray([12, 5, 7, 23]))  # Expected output: True
← Back to All Questions