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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Number of Subsequences With Equal GCD

Difficulty: Hard

Problem Description

You are given an integer array nums. Your task is to find the number of pairs of non-empty subsequences (seq1, seq2) of nums that satisfy the following conditions:

  • The subsequences seq1 and seq2 are disjoint, meaning no index of nums is common between them.
  • The GCD of the elements of seq1 is equal to the GCD of the elements of seq2.

Return the total number of such pairs modulo 10^9 + 7.

Key Insights

  • The GCD can be computed using the Euclidean algorithm which is efficient.
  • A subsequence can be generated from a set of indices, allowing for combinatorial counting.
  • The total number of subsequences of a set of size n is 2^n - 1 (excluding the empty subsequence).
  • We can group subsequences by their GCD values to count valid pairs.

Space and Time Complexity

Time Complexity: O(n * max_val * log(max_val)), where n is the length of nums and max_val is the maximum value in nums. Space Complexity: O(max_val), for storing the counts of subsequences based on their GCDs.

Solution

To solve the problem, we can utilize a dynamic programming approach combined with number theory concepts. We will:

  1. Count the occurrences of each number in the input array nums.
  2. Calculate the number of subsequences for each possible GCD by iterating through each number and updating the counts of subsequences for their multiples.
  3. For each GCD, compute the number of valid pairs of subsequences that can be formed.
  4. Sum all valid pairs and return the result modulo 10^9 + 7.

Code Solutions

def countSubsequencesWithEqualGCD(nums):
    MOD = 10**9 + 7
    max_num = max(nums)
    count = [0] * (max_num + 1)
    
    # Count occurrences of each number
    for num in nums:
        count[num] += 1
    
    # To store number of subsequences for each gcd
    subseq_count = [0] * (max_num + 1)
    
    # Calculate subsequences for each possible GCD
    for g in range(max_num, 0, -1):
        total = 0
        for multiple in range(g, max_num + 1, g):
            total += count[multiple]
        
        if total > 0:
            subseq_count[g] = (pow(2, total, MOD) - 1) % MOD
        
        # Count pairs of subsequences with the same GCD
        for multiple in range(2 * g, max_num + 1, g):
            subseq_count[g] = (subseq_count[g] - subseq_count[multiple]) % MOD
    
    # Calculate total pairs of subsequences
    result = 0
    for g in range(1, max_num + 1):
        if subseq_count[g] > 1:
            result = (result + subseq_count[g] * (subseq_count[g] - 1) // 2) % MOD
    
    return result
← Back to All Questions