3336. Find the Number of Subsequences With Equal GCD

HardView on LeetCode

Array Math Dynamic Programming Number Theory

Time: O(n * M^2)

Space: O(M^2)

Problem Overview

Count ordered pairs of disjoint non-empty subsequences with the same GCD.

Intuition

Count ordered pairs of disjoint non-empty subsequences with the same GCD. Constraints are tiny (n, values ≤ 200), so track every possible GCD pair while scanning the array. dp[x][y] = number of ways to assign processed elements so the first subsequence has GCD x and the second has GCD y (0 means that subsequence is still empty).

Algorithm

1Let M = max(nums). Initialize dp[0][0] = 1 (both subsequences empty).
2For each num, build a fresh table newDp. For every existing state (x, y) with count c:
3 • Skip num → add c to newDp[x][y].
4 • Append to first → add c to newDp[gcd(x, num)][y] (gcd(0, num) = num).
5 • Append to second → add c to newDp[x][gcd(y, num)].
6All additions are modulo 10^9+7; replace dp with newDp.
7Answer = sum of dp[g][g] for g = 1 … M (both non-empty and equal GCD).

Example Walkthrough

Input: nums = [10, 20, 30]

1.Start dp[0][0] = 1.
2.After 10: can leave both empty, put 10 in first (GCD 10), or put 10 in second.
3.After 20 and 30: the only equal non-empty pairs are ([10], [20,30]) and ([20,30], [10]) — both have GCD 10.
4.Summing dp[g][g] for g ≥ 1 yields 2.

Output: 2

Common Pitfalls

•Subsequences must be index-disjoint — each element goes to at most one of the two sequences (or neither).
•Do not count dp[0][0]; both subsequences must be non-empty (sum from g = 1).
•Use a separate newDp table each step — updating in place double-counts transitions.
•gcd(0, x) = x is required so the first element placed into an empty subsequence sets its GCD.

3336.cs

// Approach: DP over disjoint subsequence pairs. dp[x][y] = ways to form two subsequences
// with GCDs x and y (0 = empty). For each num: skip it, append to first, or append to second.
// Answer is sum of dp[g][g] for g >= 1 (both non-empty with equal GCD), mod 1e9+7.
// Time: O(n * M^2) Space: O(M^2) where M = max(nums)
public class Solution
{
    private const int MOD = 1_000_000_007;

    public int SubsequencePairCount(int[] nums)
    {
        int n = nums.Length;
        int maxNum = 0;
        foreach (var num in nums)
        {
            if (num > maxNum)
                maxNum = num;
        }

        int[,] dp = new int[maxNum + 1, maxNum + 1];
        dp[0, 0] = 1;

        foreach (var num in nums)
        {
            int[,] newDp = new int[maxNum + 1, maxNum + 1];
            for (int x = 0; x <= maxNum; ++x)
            {
                for (int y = 0; y <= maxNum; ++y)
                {
                    // 1. Skip `num`.
                    newDp[x, y] = (newDp[x, y] + dp[x, y]) % MOD;
                    // 2. Pick `num` in the first subsequence.
                    int newX = Gcd(x, num);
                    newDp[newX, y] = (newDp[newX, y] + dp[x, y]) % MOD;
                    // 3. Pick `num` in the second subsequence.
                    int newY = Gcd(y, num);
                    newDp[x, newY] = (newDp[x, newY] + dp[x, y]) % MOD;
                }
            }
            dp = newDp;
        }

        int ans = 0;
        for (int g = 1; g <= maxNum; ++g)
            ans = (ans + dp[g, g]) % MOD;

        return ans;
    }

    private int Gcd(int a, int b)
    {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

Was this solution helpful?