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

Number of Different Subsequences GCDs

Number: 1947

Difficulty: Hard

Paid? No

Companies: Akuna Capital

Problem Description

Given an array of positive integers, return the number of distinct greatest common divisors (GCDs) that can be obtained from all non-empty subsequences of the array.

Key Insights

  • The number of subsequences is too large to enumerate, so instead consider candidates for the GCD.
  • For each candidate d, if it divides some elements, then check if there exists a subsequence whose GCD is exactly d.
  • By iterating over the multiples of d and computing their GCD, we can determine if d is achievable.
  • Use a frequency array to quickly check the presence of numbers and optimize the multiple iterations.

Space and Time Complexity

Time Complexity: O(max(nums) * log(max(nums))) (The inner loop iterates over multiples, leading to a harmonic sum complexity.) Space Complexity: O(max(nums)) (For the frequency array.)

Solution

The solution first builds a frequency table for all numbers in the array up to the maximum value. Then, for each potential GCD candidate d from 1 to max(nums), iterate through its multiples. For each multiple present in the array, update a running GCD value. If the running GCD becomes equal to d, then d is a valid GCD that can be obtained from some subsequence, so increment the count. This leverages the arithmetic properties of the GCD and avoids exploring all possible subsequences.

Code Solutions

def countDifferentSubsequenceGCDs(nums):
    import math
    max_val = max(nums)
    freq = [0] * (max_val + 1)
    # Build frequency array for all numbers in nums
    for num in nums:
        freq[num] += 1
    
    result = 0
    # Iterate over all possible divisors from 1 to max_val
    for d in range(1, max_val + 1):
        current_gcd = 0
        # Check every multiple of d
        multiple = d
        while multiple <= max_val:
            if freq[multiple]:
                current_gcd = math.gcd(current_gcd, multiple)
                # Early exit if the current_gcd matches candidate d
                if current_gcd == d:
                    break
            multiple += d
        if current_gcd == d:
            result += 1
    return result

# Example usage:
print(countDifferentSubsequenceGCDs([6, 10, 3]))  # Expected output: 5
← Back to All Questions