Count Subsequence Pairs With Equal GCD — DP Explained Step by Step

Introduction

Some problems test whether you know a formula. This one tests whether you can see structure where none seems to exist. "Count Subsequence Pairs With Equal GCD" looks intimidating on paper — two disjoint groups, matching GCDs, counting all valid pairs — but it's actually a masterclass in a specific interview skill: turning an exponential search space into a polynomial one by figuring out exactly what information you need to remember.

This is a favorite in interviews for senior and staff-level roles because it doesn't test whether you memorized GCD or subsequence definitions. It tests whether you can ask the right question: "what's the minimum state I need to carry forward?" Once you internalize that skill here, you'll start spotting it in dozens of other DP problems — partition problems, subset-sum variants, and counting problems in general.

Problem Overview

You're given an array of positive integers. You need to split the array's elements into two groups — call them Group 1 and Group 2 — with two rules:

1. Disjoint and non-empty: no index can belong to both groups, and both groups must have at least one element (leftover elements are simply excluded from both — think of it as a third "bench").
2. Equal GCD: the greatest common divisor of all elements in Group 1 must equal the greatest common divisor of all elements in Group 2.

You must count every valid way to form such a pair of groups, modulo 10^9 + 7. Note that swapping which group is "Group 1" and which is "Group 2" counts as a distinct pair — order matters.

Example

Take nums = [10, 20, 30].

• Put 10 in Group 1 → GCD = 10. Put 20, 30 in Group 2 → GCD(20, 30) = 10. Match.
• Swap: 20, 30 in Group 1, 10 in Group 2. Also a match.

That's the only structure that works here, so the answer is 2.

Now sanity-check with nums = [1, 1, 1, 1]. Since GCD of any non-empty subset of 1's is always 1, every way of splitting the four elements into two non-empty, disjoint groups (with leftovers allowed on the bench) counts. We'll prove below that this comes out to exactly 50, which is a great way to verify any implementation before trusting it on harder inputs.

Intuition

The instinctive approach is to think in terms of subsequences: enumerate every subsequence for Group 1, then every subsequence of what's left for Group 2, compute GCDs, and compare. That's the shape of the problem as stated — but it's also a trap. The number of subsequence pairs grows explosively, and most of that enumeration is wasted work.

The reframe that unlocks this problem: stop thinking about "picking subsequences" and start thinking about "making a decision at each index." Walk through the array left to right. For each element, there are exactly three things that can happen to it:

1. It joins Group 1.
2. It joins Group 2.
3. It joins neither (the "bench").

Every possible pair of disjoint subsequences corresponds to exactly one sequence of these per-element decisions, and every sequence of decisions corresponds to exactly one pair of subsequences. That's a clean bijection — so instead of counting subsequence pairs, we can count decision sequences, which is a much more DP-friendly shape.

The second insight is even more important: to check the final condition (equal GCDs), you don't need to remember which elements went into each group. You only need to remember the current running GCD of each group. That's it. Two numbers. Since array values are bounded (say, at most 200), each running GCD is bounded too, so the entire "memory" of the process fits in a small 2D grid: dp[a][b] = number of ways to reach a state where Group 1's running GCD is a and Group 2's running GCD is b.

One elegant detail makes this work cleanly: GCD(0, x) = x by convention. So we use 0 to represent "this group is still empty," and when the first element joins an empty group, the running GCD update formula (gcd(current, x)) naturally turns into x — no special-casing needed.

Brute Force Solution

Idea: For every element, literally try all three assignments (Group 1, Group 2, bench), recursively, and at the end check whether the two groups are non-empty and share a GCD.

Algorithm:

1. Recurse over each index with three branches.
2. At the base case (end of array), compute GCD of each group.
3. If both are non-empty and GCDs match, count it.

Advantages: Trivially correct, easy to write in a handful of lines, perfect for validating a faster solution on tiny inputs.

Disadvantages: Time complexity is O(3^n). At n = 15 that's already ~14 million branches; at n = 200 (the real constraint), it's computationally impossible.

Complexity: Time O(3^n), Space O(n) for recursion depth.

Optimal Solution

We build a DP table dp[a][b], where a ranges over possible GCD values for Group 1 and b over possible GCD values for Group 2 (both from 0 to maxVal, where 0 means "empty").

Initialization: dp[0][0] = 1 — before touching any element, there's exactly one state: both groups empty.

Transition: For each element x in the array, we make a copy of the current table (call it next_dp), then for every state (a, b) with a nonzero count in the current table:

• Bench x: already represented, since next_dp starts as a copy of dp.
• Assign x to Group 1: add dp[a][b] to next_dp[gcd(a, x)][b].
• Assign x to Group 2: add dp[a][b] to next_dp[a][gcd(b, x)].

Then dp = next_dp for the next iteration.

Why copy instead of updating in place? Because if you update the live table while iterating over it, the same element could get "used twice" — once to update a cell, and then that updated cell gets processed again in the same pass, effectively letting x join a group more than once.

Reading the answer: After processing all elements, dp[g][g] (for g >= 1) counts the number of ways both groups ended up with running GCD exactly g. We start at g = 1, not g = 0, because dp[0][0] represents "both groups still empty" — which violates the non-empty requirement. Since a non-empty group can never have GCD 0, starting the diagonal sum at g = 1 automatically excludes the all-empty case.

Answer = sum(dp[g][g] for g in 1..maxVal) % (10^9 + 7).

Visualizing the grid

	b=0	b=1	b=2	...
a=0	both empty	G2 has gcd 1	G2 has gcd 2	...
a=1	G1 has gcd 1	both gcd 1 ✅
a=2	G1 has gcd 2		both gcd 2 ✅

The diagonal (✅ cells) is exactly what we want to sum.

Python Code

from math import gcd

MOD = 10**9 + 7

def count_pairs_equal_gcd(nums: list[int]) -> int:
    max_val = max(nums)

    # dp[a][b] = number of ways group1 has running gcd a, group2 has running gcd b
    # index 0 means "group is still empty"
    dp = [[0] * (max_val + 1) for _ in range(max_val + 1)]
    dp[0][0] = 1

    for x in nums:
        next_dp = [row[:] for row in dp]  # copy: handles "bench x" for free

        for a in range(max_val + 1):
            for b in range(max_val + 1):
                ways = dp[a][b]
                if ways == 0:
                    continue

                # assign x to group 1
                new_a = gcd(a, x)
                next_dp[new_a][b] = (next_dp[new_a][b] + ways) % MOD

                # assign x to group 2
                new_b = gcd(b, x)
                next_dp[a][new_b] = (next_dp[a][new_b] + ways) % MOD

        dp = next_dp

    # sum the diagonal, skipping g=0 (both groups empty)
    return sum(dp[g][g] for g in range(1, max_val + 1)) % MOD


def demo():
    assert count_pairs_equal_gcd([10, 20, 30]) == 2
    assert count_pairs_equal_gcd([1, 1, 1, 1]) == 50
    assert count_pairs_equal_gcd([5]) == 0  # can't form two non-empty groups
    print("all checks passed")


if __name__ == "__main__":
    demo()

Code Walkthrough

• max_val = max(nums): bounds the grid size — GCDs never exceed the largest element in the array.
• dp[0][0] = 1: the seed state, both groups empty, before any element is processed.
• next_dp = [row[:] for row in dp]: a deep-enough copy (each row is a fresh list) so writes for element x don't leak into reads for the same element.
• Inner double loop over a, b: iterates every state currently reachable; if ways == 0: continue skips dead cells purely for speed — no cell needs to be visited if it's never been reached.
• new_a = gcd(a, x): computes what Group 1's running GCD becomes if x joins it; because gcd(0, x) == x, an empty group correctly "activates" with its first element.
• Two update lines: represent the two live "doors" (bench is implicit via the copy).
• Final sum: reads off the diagonal starting at index 1, which is exactly the set of states where both groups are non-empty and share a GCD.

Dry Run

nums = [10, 20, 30], max_val = 30.

Start: dp[0][0] = 1.

Process x=10:

• From (0,0) with ways=1: assign to G1 → (10, 0) += 1; assign to G2 → (0, 10) += 1.
• After: dp[0][0]=1, dp[10][0]=1, dp[0][10]=1.

Process x=20:

• From (0,0): → (20,0) += 1, (0,20) += 1.
• From (10,0): gcd(10,20)=10 → (10,0) += 1 (bench, already copied) plus assign G1 → (10,0) += 1 → total dp[10][0]=2; assign G2 → (10,20) += 1.
• From (0,10): assign G1 → (20,10) += 1; assign G2: gcd(10,20)=10 → (0,10) += 1 (already copied, now 2).

Process x=30: continuing this process (full table has many entries), the two paths that survive to the diagonal are:

• Group 1 = {10}, Group 2 = {20,30} → both end at gcd 10 → dp[10][10] += 1.
• Group 1 = {20,30}, Group 2 = {10} → also dp[10][10] += 1.

Final: dp[10][10] = 2, all other diagonal entries are 0. Sum = 2. Matches our hand-traced example.

Complexity Analysis

• Time: O(n * V^2) where V is the max value in the array (grid dimension). With n <= 200 and V <= 200, that's roughly 200 * 200 * 200 ≈ 8,000,000 operations — fast in practice.
• Space: O(V^2) for the DP grid (plus its copy during transitions).
• Why correct: the bijection between "decision sequences" and "pairs of disjoint subsequences" is exact — every element makes exactly one of three choices, and every combination of choices across all elements produces exactly one valid (or invalid, if a group ends empty) pair. The DP just accumulates counts along that bijection without ever double-counting, because each element is folded into next_dp from a frozen snapshot of dp.

Alternative Solutions

You could shrink the grid using the fact that only divisors of elements actually in the array matter, rather than every value from 0 to max_val. This uses less memory when the array has few small max values but many divisors are already sparse — but in practice for n, V <= 200, the dense grid is simpler and fast enough, so this optimization isn't worth the added bookkeeping unless constraints get much larger. This is a good example of when the "obviously smarter" approach isn't worth building — the state space is already small enough that dense storage wins on simplicity.

Edge Cases

• Empty array: no elements to assign, answer is 0 (can't form two non-empty groups).
• Single element: cannot split into two non-empty groups, answer is 0. dp[g][g] for g >= 1 never fires because one group always stays at 0.
• All duplicate values (e.g., [1,1,1,1]): handled naturally since assignment is by index, not value — verified against the hand-computed answer of 50.
• Maximum values (elements at the upper constraint bound): grid size scales with max_val, so very large max values increase memory; watch for this if constraints change.
• All elements equal to 1: every non-empty group has GCD 1, so this becomes a pure counting-of-partitions problem — a great sanity check because it can be verified by hand with inclusion-exclusion.

Common Mistakes

1. Updating the DP table in place instead of writing into a copy — causes an element to be counted as joining a group more than once.
2. Forgetting the GCD(0, x) = x convention — leads to incorrectly special-casing "first element into a group" instead of letting the formula handle it.
3. Starting the diagonal sum at g = 0 — incorrectly includes the "both groups empty" state, inflating the answer.
4. Not applying modulo on every addition — waiting until the end causes integer overflow behavior differences or, in languages with fixed-width integers, silent corruption.
5. Sizing the grid off the array length instead of the max element value — the GCD state space is bounded by value magnitude, not array length.
6. Confusing "disjoint" with "distinct values" — disjoint refers to index positions, not values; duplicate values are completely fine as long as they occupy different indices.

Interview Questions

• How would the solution change if the two groups could overlap?
• What if we wanted the GCD to be a specific target value g, not "any equal value"?
• How would you adapt this for three groups needing pairwise equal GCDs?
• Can you bound the grid using only divisors present in the array to reduce space?
• What's the time complexity if the array values could be much larger (say, up to 10^9)?

Similar Problems

• LeetCode 878 — Nth Magical Number: also relies heavily on GCD/LCM reasoning.
• LeetCode 1819 — Number of Different Subsequences GCDs: same core building block (GCD tracking), different counting objective.
• LeetCode 494 — Target Sum: same "three choices per element, DP over running state" pattern, with sum instead of GCD as the tracked state.
• LeetCode 416 — Partition Equal Subset Sum: same disjoint-partition flavor, using sum equality instead of GCD equality.

Key Takeaways

The core lesson isn't about GCDs at all — it's about state compression. Whenever a counting problem seems to require tracking "which exact elements" went somewhere, ask whether a much smaller summary (a running GCD, a running sum, a running XOR) actually suffices to answer the final question. Once you find that summary, the exponential search collapses into a polynomial DP table, and the three-choices-per-element framing turns a scary enumeration problem into an ordinary Bellman-style fill.

Watch the Video

For the full step-by-step walkthrough with diagrams and the live code build, watch the video here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where each problem gets a full teardown — the intuition first, then brute force, then the optimal approach, all the way down to a clean, production-quality Python implementation. The goal isn't to memorize solutions; it's to build the pattern-recognition muscle that lets you solve problems you've never seen before.

Call To Action

If this breakdown helped the DP click, subscribe on YouTube for the daily walkthroughs, and subscribe to the Substack for the full written version delivered straight to your inbox. Drop a comment with the problem you want tackled next, and share this with a friend prepping for interviews.

---

    for x in nums:
        new = [row[:] for row in dp]
        for a in range(M):
            for b in range(M):
                v = dp[a][b]
                if v:
                    g1 = gcd(a, x)
                    g2 = gcd(b, x)
                    new[g1][b] = (new[g1][b] + v) % MOD
                    new[a][g2] = (new[a][g2] + v) % MOD
        dp = new