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.
This approach involves efficiently keeping track of potential GCDs by iterating through all possible numbers. We calculate the number of subsequences for each possible GCD and use combinatorial principles to find disjoint subsequences.
In this Python solution, we iterate over every possible GCD value and calculate the number of subsequences that could result in each GCD. We calculate powers of 2 to get all possible non-empty subsequences and compute the result for disjoint pairs.
Time Complexity: O(n * log(max_num)) where n is the number of elements in the input.
Space Complexity: O(max_num)
This approach leverages dynamic programming. We maintain a dp table where dp[i][g] represents the number of subsequences ending at index i with GCD g. This method incrementally builds up the solution using possible divisors.
In this Java solution, we use recursion with memoization to explore different possible subsequences that share the same GCD. The function 'pow' is used to compute the power mod iteratively to prevent overflow.
Java
Time Complexity: O(n * log(max_num))
Space Complexity: O(max_num)
| Approach | Complexity |
|---|---|
| Efficient Counting with GCD Tracking | Time Complexity: O(n * log(max_num)) where n is the number of elements in the input. |
| Dynamic Programming for GCD Subsequences | Time Complexity: O(n * log(max_num)) |
| 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 |
Leetcode Weekly Contest 421 | 3336. Find the Number of Subsequences With Equal GCD | CodeFod • CodeFod • 454 views views
Watch 3 more video solutions →Practice Find the Number of Subsequences With Equal GCD with our built-in code editor and test cases.
Practice on FleetCode