Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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 seq1 and seq2 are disjoint, meaning no index of nums is common between them. The GCD of the elements of 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Dynamic Programming
[1,2,3,4]
[10,20,30]
[1,1,1,1]
find-greatest-common-divisor-of-array)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
class Solution {
public int subsequencePairCount(int[] nums) {
final int maxNum = Arrays.stream(nums).max().getAsInt();
Integer[][][] mem = new Integer[nums.length][maxNum + 1][maxNum + 1];
return subsequencePairCount(nums, 0, 0, 0, mem);
}
private static final int MOD = 1_000_000_007;
private int subsequencePairCount(int[] nums, int i, int x, int y, Integer[][][] mem) {
if (i == nums.length)
return (x > 0 && x == y) ? 1 : 0;
if (mem[i][x][y] != null)
return mem[i][x][y];
// 1. Skip nums[i]
final int skip = subsequencePairCount(nums, i + 1, x, y, mem);
// 2. Pick nums[i] in the first subsequence
final int take1 = subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
// 3. Pick nums[i] in the second subsequence
final int take2 = subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
return mem[i][x][y] = (int) (((long) skip + take1 + take2) % MOD);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
// Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
package main
import "slices"
// https://space.bilibili.com/206214
const mod = 1_000_000_007
const mx = 201
var lcms [mx][mx]int
var pow2, pow3, mu [mx]int
func init() {
for i := 1; i < mx; i++ {
for j := 1; j < mx; j++ {
lcms[i][j] = lcm(i, j)
}
}
pow2[0], pow3[0] = 1, 1
for i := 1; i < mx; i++ {
pow2[i] = pow2[i-1] * 2 % mod
pow3[i] = pow3[i-1] * 3 % mod
}
mu[1] = 1
for i := 1; i < mx; i++ {
for j := i * 2; j < mx; j += i {
mu[j] -= mu[i]
}
}
}
func subsequencePairCount(nums []int) int {
m := slices.Max(nums)
// cnt[i] 表示 nums 中的 i 的倍数的个数
cnt := make([]int, m+1)
for _, x := range nums {
cnt[x]++
}
for i := 1; i <= m; i++ {
for j := i * 2; j <= m; j += i {
cnt[i] += cnt[j] // 统计 i 的倍数的个数
}
}
f := make([][]int, m+1)
for g1 := 1; g1 <= m; g1++ {
f[g1] = make([]int, m+1)
for g2 := 1; g2 <= m; g2++ {
l := lcms[g1][g2]
c := 0
if l <= m {
c = cnt[l]
}
c1, c2 := cnt[g1], cnt[g2]
f[g1][g2] = (pow3[c]*pow2[c1+c2-c*2] - pow2[c1] - pow2[c2] + 1) % mod
}
}
// 倍数容斥
ans := 0
for i := 1; i <= m; i++ {
for j := 1; j <= m/i; j++ {
for k := 1; k <= m/i; k++ {
ans += mu[j] * mu[k] * f[j*i][k*i]
}
}
}
return (ans%mod + mod) % mod // 保证 ans 非负
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func lcm(a, b int) int {
return a / gcd(a, b) * b
}
func subsequencePairCount2(nums []int) int {
const mod = 1_000_000_007
n := len(nums)
m := slices.Max(nums)
memo := make([][][]int, n)
for i := range memo {
memo[i] = make([][]int, m+1)
for j := range memo[i] {
memo[i][j] = make([]int, m+1)
for k := range memo[i][j] {
memo[i][j][k] = -1
}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i < 0 {
if j == k {
return 1
}
return 0
}
p := &memo[i][j][k]
if *p < 0 {
*p = (dfs(i-1, j, k) + dfs(i-1, gcd(j, nums[i]), k) + dfs(i-1, j, gcd(k, nums[i]))) % mod
}
return *p
}
// 减去两个子序列都是空的情况
return (dfs(n-1, 0, 0) - 1 + mod) % mod
}
# Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
class Solution:
def subsequencePairCount(self, nums: list[int]) -> int:
MOD = 1_000_000_007
@functools.lru_cache(None)
def dp(i: int, x: int, y: int) -> int:
if i == len(nums):
return int(x > 0 and x == y)
# 1. Skip nums[i]
skip = dp(i + 1, x, y)
# 2. Pick nums[i] in the first subsequence
take1 = dp(i + 1, math.gcd(x, nums[i]), y)
# 3. Pick nums[i] in the second subsequence
take2 = dp(i + 1, x, math.gcd(y, nums[i]))
return (skip + take1 + take2) % MOD
return dp(0, 0, 0)
// Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
// class Solution {
// public int subsequencePairCount(int[] nums) {
// final int maxNum = Arrays.stream(nums).max().getAsInt();
// Integer[][][] mem = new Integer[nums.length][maxNum + 1][maxNum + 1];
// return subsequencePairCount(nums, 0, 0, 0, mem);
// }
//
// private static final int MOD = 1_000_000_007;
//
// private int subsequencePairCount(int[] nums, int i, int x, int y, Integer[][][] mem) {
// if (i == nums.length)
// return (x > 0 && x == y) ? 1 : 0;
// if (mem[i][x][y] != null)
// return mem[i][x][y];
// // 1. Skip nums[i]
// final int skip = subsequencePairCount(nums, i + 1, x, y, mem);
// // 2. Pick nums[i] in the first subsequence
// final int take1 = subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
// // 3. Pick nums[i] in the second subsequence
// final int take2 = subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
// return mem[i][x][y] = (int) (((long) skip + take1 + take2) % MOD);
// }
//
// private int gcd(int a, int b) {
// return b == 0 ? a : gcd(b, a % b);
// }
// }
// Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3336: Find the Number of Subsequences With Equal GCD
// class Solution {
// public int subsequencePairCount(int[] nums) {
// final int maxNum = Arrays.stream(nums).max().getAsInt();
// Integer[][][] mem = new Integer[nums.length][maxNum + 1][maxNum + 1];
// return subsequencePairCount(nums, 0, 0, 0, mem);
// }
//
// private static final int MOD = 1_000_000_007;
//
// private int subsequencePairCount(int[] nums, int i, int x, int y, Integer[][][] mem) {
// if (i == nums.length)
// return (x > 0 && x == y) ? 1 : 0;
// if (mem[i][x][y] != null)
// return mem[i][x][y];
// // 1. Skip nums[i]
// final int skip = subsequencePairCount(nums, i + 1, x, y, mem);
// // 2. Pick nums[i] in the first subsequence
// final int take1 = subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
// // 3. Pick nums[i] in the second subsequence
// final int take2 = subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
// return mem[i][x][y] = (int) (((long) skip + take1 + take2) % MOD);
// }
//
// private int gcd(int a, int b) {
// return b == 0 ? a : gcd(b, a % b);
// }
// }
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.