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

Find the Number of Subsequences With Equal GCD

Number: 3608

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of integers nums, count the number of ordered pairs of non-empty subsequences (seq1, seq2) such that the two subsequences are disjoint (i.e. no index is reused) and the greatest common divisor (GCD) of the numbers in seq1 equals the GCD of the numbers in seq2. Return the answer modulo 10^9+7.

Key Insights

  • Recognize that each element can be assigned to either subsequence 1, subsequence 2, or to neither.
  • Use dynamic programming (DP) to iterate through the array and update the current GCD for each group.
  • A DP state can be defined by a pair (g1, g2) representing the GCD accumulated for subsequence 1 and subsequence 2 respectively (with 0 indicating that the subsequence is still empty).
  • When processing a new element, update the state by considering adding the element to group1 (updating g1), group2 (updating g2), or skipping it (leaving both groups unchanged).
  • After processing all elements, sum over all DP states where both groups are nonempty (g1, g2 ≠ 0) and have equal GCD.
  • The DP avoids considering 3^n complete assignments explicitly while ensuring disjointness by construction.

Space and Time Complexity

Time Complexity: O(n * MAX_VAL^2), where n is the number of elements in nums and MAX_VAL (≈200) is the maximum possible value in nums. Space Complexity: O(MAX_VAL^2) for storing DP states.

Solution

We use a dynamic programming approach with a dictionary (or 2D array) where each state is a pair (g1, g2) indicating the current GCD for subsequence 1 and subsequence 2, respectively. Initially, both subsequences are empty (represented by 0). For each number in the array, we have three choices:

  1. Do not include the number in either subsequence.
  2. Add the number to subsequence 1, updating its GCD.
  3. Add the number to subsequence 2, updating its GCD. After processing all elements, we sum up the ways in all states where the GCDs are equal and nonzero (ensuring that neither subsequence is empty). This process effectively counts all ways to form a pair of disjoint subsequences meeting the desired condition.

Code Solutions

from math import gcd
MOD = 10**9 + 7

def countPairs(nums):
    # dp is a dictionary with key: (g1, g2) and value: number of assignments reaching that state.
    dp = {(0, 0): 1}
    for num in nums:
        new_dp = {}
        for (g1, g2), ways in dp.items():
            # Option 1: Skip the current number (assign to neither subsequence)
            new_dp[(g1, g2)] = (new_dp.get((g1, g2), 0) + ways) % MOD

            # Option 2: Add current num to subsequence 1
            new_g1 = num if g1 == 0 else gcd(g1, num)
            new_dp[(new_g1, g2)] = (new_dp.get((new_g1, g2), 0) + ways) % MOD

            # Option 3: Add current num to subsequence 2
            new_g2 = num if g2 == 0 else gcd(g2, num)
            new_dp[(g1, new_g2)] = (new_dp.get((g1, new_g2), 0) + ways) % MOD
        dp = new_dp

    ans = 0
    # Consider only the DP states where both subsequences are non-empty (nonzero gcd)
    # and the gcd values are equal.
    for (g1, g2), ways in dp.items():
        if g1 == g2 and g1 != 0:
            ans = (ans + ways) % MOD
    return ans

# Example test-cases:
print(countPairs([1, 2, 3, 4]))  # Expected output: 10
print(countPairs([10, 20, 30]))  # Expected output: 2
print(countPairs([1, 1, 1, 1]))  # Expected output: 50
← Back to All Questions