Watch 4 video solutions for Find the Number of Subsequences With Equal GCD, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by CodeFod has 454 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 200Problem Overview: Given an integer array, count how many pairs of non‑empty subsequences produce the same greatest common divisor (GCD). The challenge is that the number of subsequences grows exponentially, so you cannot enumerate them directly. The goal is to track GCD values formed by subsequences and combine counts efficiently.
Approach 1: Efficient Counting with GCD Tracking (O(n * M log M) time, O(M) space)
Track how many subsequences produce each possible GCD while iterating through the array. For each number x, extend previously formed subsequences by computing gcd(prev_gcd, x). Maintain a frequency map where the key is the GCD value and the value is the number of subsequences producing that GCD. This works because the GCD of a subsequence can be updated incrementally. Once counts for each GCD are known, compute how many pairs of subsequences share the same GCD using combinatorics (for example count * (count - 1) / 2). The repeated gcd operations are fast, so the overall complexity stays manageable. This technique relies heavily on properties of number theory and incremental aggregation.
Approach 2: Dynamic Programming for GCD Subsequences (O(n * M^2 log M) time, O(M^2) space)
Model the problem with dynamic programming where the state represents the GCD values of two subsequences being built simultaneously. When processing each element, decide whether to add it to the first subsequence, the second subsequence, or skip it. Update the state using gcd(current_gcd, nums[i]). This creates a transition graph over possible GCD pairs. At the end, sum the states where both subsequences have the same non-zero GCD. The approach is more explicit and easier to reason about, but the state space grows with the maximum value in the array. This technique demonstrates classic dynamic programming over subsequence construction combined with repeated math operations.
Recommended for interviews: The GCD tracking approach is the one most interviewers expect. It shows you understand how subsequence GCDs evolve and how to compress exponential possibilities into aggregated counts. The DP formulation demonstrates correctness but is heavier in both time and memory.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Efficient Counting with GCD Tracking | O(n * M log M) | O(M) | General case and large arrays where subsequences cannot be enumerated |
| Dynamic Programming for GCD Subsequences | O(n * M^2 log M) | O(M^2) | When explicitly modeling two subsequences and reasoning about transitions |