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:
seq1 and seq2 are disjoint, meaning no index of nums is common between them.seq1 is equal to the GCD of the elements of seq2.Return the total number of such pairs.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4]
Output: 10
Explanation:
The subsequence pairs which have the GCD of their elements equal to 1 are:
([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])([1, 2, 3, 4], [1, 2, 3, 4])Example 2:
Input: nums = [10,20,30]
Output: 2
Explanation:
The subsequence pairs which have the GCD of their elements equal to 10 are:
([10, 20, 30], [10, 20, 30])([10, 20, 30], [10, 20, 30])Example 3:
Input: nums = [1,1,1,1]
Output: 50
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 200For #3336 Find the Number of Subsequences With Equal GCD, the key challenge is counting pairs of subsequences whose gcd values end up equal. A brute force approach that enumerates all subsequences is infeasible because the number of subsequences grows exponentially.
A common strategy is to use dynamic programming with GCD states. While iterating through the array, track how the GCD evolves for subsequences being formed. Each state represents the current gcd values of two subsequences. When processing a new element, you can either skip it, add it to the first subsequence, or add it to the second subsequence, updating the GCD using gcd(prev, value).
The answer is obtained by summing states where the two computed GCDs become equal and non‑zero. Since GCD values are bounded by the maximum array value, the DP state space remains manageable.
This approach leverages number theory properties of GCD and runs in approximately O(n × G²) time where G is the maximum possible GCD value, with O(G²) space for the DP table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with GCD States | O(n × G²) | O(G²) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming to store number of subsequences up till index <code>i</code> with GCD <code>g1</code> and <code>g2</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving subsequence counting, dynamic programming, and GCD properties are common in advanced coding interviews. While this exact question may not always appear, similar number theory and DP combinations are frequently tested.
A 2D dynamic programming table or hash map keyed by GCD pairs works well. Each state represents the current GCD values of two subsequences being built while iterating through the array.
The optimal approach uses dynamic programming combined with GCD transitions. It tracks possible GCD values of subsequences as the array is processed and counts pairs of subsequences that end with the same GCD.
Number theory is essential because the GCD operation determines how subsequence values combine. Using the mathematical property gcd(a, b) = gcd(gcd(a, b), c) allows efficient DP transitions.