Find the Number of Subsequences With Equal GCD
HardUpdated: Aug 2, 2025
Practice on:
Problem
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:
- The subsequences
seq1andseq2are disjoint , meaning no index ofnumsis common between them. - The GCD of the elements of
seq1is equal to the GCD of the elements ofseq2.
Return the total number of such pairs.
Since the answer may be very large, return it modulo 10^9 + 7.
Examples
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] <= 200
Solution
Method 1 – Inclusion-Exclusion with GCD Counting
Intuition
For each possible GCD value, count the number of subsequences whose GCD is exactly that value. For each such group, the number of ways to pick two disjoint non-empty subsequences is (2^cnt - 1)^2 - (2^{cnt} - 1), where cnt is the number of elements divisible by the GCD. We use inclusion-exclusion to avoid overcounting subsequences with GCDs that are multiples of the current value.
Approach
- Count the frequency of each number in nums.
- For each possible GCD g from max(nums) down to 1:
- Count how many numbers in nums are divisible by g (call this cnt).
- The total number of non-empty subsequences of these cnt numbers is 2^cnt - 1.
- Use inclusion-exclusion: subtract the counts for all multiples of g greater than g.
- Store the number of subsequences with GCD exactly g.
- For each g, the number of valid pairs is f[g] * (f[g] - 1), where f[g] is the number of non-empty subsequences with GCD g.
- Sum over all g and return the result modulo 1e9+7.
Code
C++
class Solution {
public:
int numberOfSubsequences(vector<int>& nums) {
const int MOD = 1e9 + 7;
int mx = *max_element(nums.begin(), nums.end());
vector<int> cnt(mx + 1);
for (int x : nums) cnt[x]++;
vector<int> f(mx + 1);
vector<int> pow2(nums.size() + 1, 1);
for (int i = 1; i <= nums.size(); ++i) pow2[i] = (pow2[i-1] * 2LL) % MOD;
for (int g = mx; g >= 1; --g) {
int c = 0;
for (int k = g; k <= mx; k += g) c += cnt[k];
if (c == 0) continue;
long long total = (pow2[c] - 1 + MOD) % MOD;
for (int k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
f[g] = total;
}
long long ans = 0;
for (int g = 1; g <= mx; ++g) {
if (f[g] >= 2) ans = (ans + f[g] * (f[g] - 1LL)) % MOD;
}
return (int)ans;
}
};
Go
func numberOfSubsequences(nums []int) int {
mod := int(1e9 + 7)
mx := 0
for _, x := range nums {
if x > mx {
mx = x
}
}
cnt := make([]int, mx+1)
for _, x := range nums {
cnt[x]++
}
f := make([]int, mx+1)
pow2 := make([]int, len(nums)+1)
pow2[0] = 1
for i := 1; i <= len(nums); i++ {
pow2[i] = pow2[i-1] * 2 % mod
}
for g := mx; g >= 1; g-- {
c := 0
for k := g; k <= mx; k += g {
c += cnt[k]
}
if c == 0 {
continue
}
total := (pow2[c] - 1 + mod) % mod
for k := 2 * g; k <= mx; k += g {
total = (total - f[k] + mod) % mod
}
f[g] = total
}
ans := 0
for g := 1; g <= mx; g++ {
if f[g] >= 2 {
ans = (ans + f[g]*(f[g]-1)) % mod
}
}
return ans
}
Java
class Solution {
public int numberOfSubsequences(int[] nums) {
int MOD = 1_000_000_007;
int mx = 0;
for (int x : nums) mx = Math.max(mx, x);
int[] cnt = new int[mx + 1];
for (int x : nums) cnt[x]++;
int[] f = new int[mx + 1];
int[] pow2 = new int[nums.length + 1];
pow2[0] = 1;
for (int i = 1; i <= nums.length; ++i) pow2[i] = (int)((pow2[i-1] * 2L) % MOD);
for (int g = mx; g >= 1; --g) {
int c = 0;
for (int k = g; k <= mx; k += g) c += cnt[k];
if (c == 0) continue;
long total = (pow2[c] - 1 + MOD) % MOD;
for (int k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
f[g] = (int)total;
}
long ans = 0;
for (int g = 1; g <= mx; ++g) {
if (f[g] >= 2) ans = (ans + f[g] * (long)(f[g] - 1)) % MOD;
}
return (int)ans;
}
}
Kotlin
class Solution {
fun numberOfSubsequences(nums: IntArray): Int {
val MOD = 1_000_000_007
val mx = nums.maxOrNull() ?: 0
val cnt = IntArray(mx + 1)
for (x in nums) cnt[x]++
val f = IntArray(mx + 1)
val pow2 = IntArray(nums.size + 1) { 1 }
for (i in 1..nums.size) pow2[i] = (pow2[i-1] * 2L % MOD).toInt()
for (g in mx downTo 1) {
var c = 0
for (k in g..mx step g) c += cnt[k]
if (c == 0) continue
var total = (pow2[c] - 1 + MOD) % MOD
for (k in 2 * g..mx step g) total = (total - f[k] + MOD) % MOD
f[g] = total
}
var ans = 0L
for (g in 1..mx) {
if (f[g] >= 2) ans = (ans + f[g].toLong() * (f[g] - 1)) % MOD
}
return ans.toInt()
}
}
Python
class Solution:
def numberOfSubsequences(self, nums: list[int]) -> int:
MOD = 10**9 + 7
mx = max(nums)
cnt = [0] * (mx + 1)
for x in nums:
cnt[x] += 1
f = [0] * (mx + 1)
pow2 = [1] * (len(nums) + 1)
for i in range(1, len(nums) + 1):
pow2[i] = pow2[i-1] * 2 % MOD
for g in range(mx, 0, -1):
c = sum(cnt[k] for k in range(g, mx+1, g))
if c == 0:
continue
total = (pow2[c] - 1) % MOD
for k in range(2*g, mx+1, g):
total = (total - f[k]) % MOD
f[g] = total
ans = 0
for g in range(1, mx+1):
if f[g] >= 2:
ans = (ans + f[g] * (f[g] - 1)) % MOD
return ans
Rust
impl Solution {
pub fn number_of_subsequences(nums: Vec<i32>) -> i32 {
const MOD: i64 = 1_000_000_007;
let mx = *nums.iter().max().unwrap() as usize;
let mut cnt = vec![0; mx + 1];
for &x in &nums { cnt[x as usize] += 1; }
let mut f = vec![0i64; mx + 1];
let mut pow2 = vec![1i64; nums.len() + 1];
for i in 1..=nums.len() {
pow2[i] = pow2[i-1] * 2 % MOD;
}
for g in (1..=mx).rev() {
let mut c = 0;
let mut k = g;
while k <= mx {
c += cnt[k];
k += g;
}
if c == 0 { continue; }
let mut total = (pow2[c] - 1 + MOD) % MOD;
let mut k = 2 * g;
while k <= mx {
total = (total - f[k] + MOD) % MOD;
k += g;
}
f[g] = total;
}
let mut ans = 0i64;
for g in 1..=mx {
if f[g] >= 2 {
ans = (ans + f[g] * (f[g] - 1) % MOD) % MOD;
}
}
ans as i32
}
}
TypeScript
class Solution {
numberOfSubsequences(nums: number[]): number {
const MOD = 1e9 + 7;
const mx = Math.max(...nums);
const cnt = Array(mx + 1).fill(0);
for (const x of nums) cnt[x]++;
const f = Array(mx + 1).fill(0);
const pow2 = Array(nums.length + 1).fill(1);
for (let i = 1; i <= nums.length; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
for (let g = mx; g >= 1; --g) {
let c = 0;
for (let k = g; k <= mx; k += g) c += cnt[k];
if (c === 0) continue;
let total = (pow2[c] - 1 + MOD) % MOD;
for (let k = 2 * g; k <= mx; k += g) total = (total - f[k] + MOD) % MOD;
f[g] = total;
}
let ans = 0;
for (let g = 1; g <= mx; ++g) {
if (f[g] >= 2) ans = (ans + f[g] * (f[g] - 1)) % MOD;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(N log M)— For each divisor, we process all multiples, where N is the length of nums and M is the max value in nums. - 🧺 Space complexity:
O(M)— For the count and DP arrays, where M is the max value in nums.