Skip to content

3336. Find the Number of Subsequences With Equal GCD

Description

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.

Β 

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 <= 200
  • 1 <= nums[i] <= 200

Solutions

Solution 1: Memoization

We define a function \(\textit{dfs}(i, j, k)\) as the number of ways when considering elements with indices \(0 \sim i\), where the current GCD of the first subsequence is \(j\) and that of the second subsequence is \(k\). By convention, the GCD of an empty subsequence is \(0\), and \(\gcd(x, 0) = x\).

For the element at index \(i\), there are three choices:

  1. Skip it: transition to \(\textit{dfs}(i - 1, j, k)\);
  2. Put it into the first subsequence: transition to \(\textit{dfs}(i - 1, \gcd(\textit{nums}[i], j), k)\);
  3. Put it into the second subsequence: transition to \(\textit{dfs}(i - 1, j, \gcd(\textit{nums}[i], k))\).

Base case: when \(i \lt 0\), return \(1\) if \(j = k\), otherwise return \(0\).

The initial call \(\textit{dfs}(n - 1, 0, 0)\) counts all pairs with equal GCDs, including the case where both subsequences are empty. Therefore, we subtract \(1\) and take the result modulo \(10^9 + 7\).

The time complexity is \(O(n \times m^2 \times \log m)\), and the space complexity is \(O(n \times m^2)\), where \(n\) is the length of the array and \(m\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0:
                return int(j == k)
            return (
                dfs(i - 1, j, k)
                + dfs(i - 1, gcd(nums[i], j), k)
                + dfs(i - 1, j, gcd(nums[i], k))
            ) % mod

        mod = 10**9 + 7
        return (dfs(len(nums) - 1, 0, 0) - 1) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private int[] nums;
    private Integer[][][] f;
    private static final int MOD = 1_000_000_007;

    public int subsequencePairCount(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        int m = 0;
        for (int x : nums) {
            if (x > m) m = x;
        }
        this.f = new Integer[n + 1][m + 1][m + 1];
        return (dfs(n, 0, 0) - 1 + MOD) % MOD;
    }

    private int dfs(int i, int j, int k) {
        if (i == 0) {
            return j == k ? 1 : 0;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int x = nums[i - 1];
        int res = ((dfs(i - 1, j, k) + dfs(i - 1, gcd(x, j), k)) % MOD + dfs(i - 1, j, gcd(x, k)))
            % MOD;
        f[i][j][k] = res;
        return res;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        int m = ranges::max(nums);
        vector f(n, vector(m + 1, vector<int>(m + 1, -1)));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0) {
                return j == k;
            }
            int& res = f[i][j][k];
            if (res < 0) {
                res = ((dfs(i - 1, j, k)
                           + dfs(i - 1, gcd(nums[i], j), k))
                              % MOD
                          + dfs(i - 1, j, gcd(nums[i], k)))
                    % MOD;
            }
            return res;
        };
        return (dfs(n - 1, 0, 0) - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func subsequencePairCount(nums []int) int {
    const mod = 1_000_000_007
    n := len(nums)
    m := slices.Max(nums)
    f := make([][][]int, n)
    for i := range f {
        f[i] = make([][]int, m+1)
        for j := range f[i] {
            f[i][j] = make([]int, m+1)
            for k := range f[i][j] {
                f[i][j][k] = -1
            }
        }
    }
    var gcd func(int, int) int
    gcd = func(a, b int) int {
        if b == 0 {
            return a
        }
        return gcd(b, a%b)
    }
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i < 0 {
            if j == k {
                return 1
            }
            return 0
        }
        res := &f[i][j][k]
        if *res < 0 {
            x := nums[i]
            *res = ((dfs(i-1, j, k)+
                dfs(i-1, gcd(x, j), k))%mod +
                dfs(i-1, j, gcd(x, k))) % mod
        }
        return *res
    }
    return (dfs(n-1, 0, 0) - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function subsequencePairCount(nums: number[]): number {
    const mod = 1_000_000_007;
    const n = nums.length;
    const m = Math.max(...nums);
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: m + 1 }, () => new Array(m + 1).fill(-1)),
    );
    const gcd = (a: number, b: number): number => {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    const dfs = (i: number, j: number, k: number): number => {
        if (i < 0) {
            return j === k ? 1 : 0;
        }
        let res = f[i][j][k];
        if (res < 0) {
            const x = nums[i];
            res =
                (((dfs(i - 1, j, k) + dfs(i - 1, gcd(x, j), k)) % mod) + dfs(i - 1, j, gcd(x, k))) %
                mod;
            f[i][j][k] = res;
        }
        return res;
    };
    return (((dfs(n - 1, 0, 0) - 1) % mod) + mod) % mod;
}

Solution 2: Dynamic Programming

We can convert the memoization in Solution 1 into an iterative DP.

Define \(f[j][k]\) as the number of ways after processing the current elements such that the GCD of the first subsequence is \(j\) and that of the second is \(k\). Initially, \(f[0][0] = 1\).

For each element \(x\), transfer into a new array \(g\):

\[ \begin{aligned} g[j][k] &\mathrel{+}= f[j][k], \\ g[\gcd(j, x)][k] &\mathrel{+}= f[j][k], \\ g[j][\gcd(k, x)] &\mathrel{+}= f[j][k]. \end{aligned} \]

These correspond to skipping \(x\), putting \(x\) into the first subsequence, and putting \(x\) into the second subsequence, respectively. After processing all elements, the answer is \(\sum_{i=0}^{m} f[i][i] - 1\), taken modulo \(10^9 + 7\).

The time complexity is \(O(n \times m^2 \times \log m)\), and the space complexity is \(O(m^2)\), where \(n\) is the length of the array and \(m\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        m = max(nums)
        f = [[0] * (m + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for x in nums:
            g = [[0] * (m + 1) for _ in range(m + 1)]
            for j in range(m + 1):
                for k in range(m + 1):
                    if f[j][k] == 0:
                        continue
                    v = f[j][k]
                    g[j][k] = (g[j][k] + v) % mod
                    gj, gk = gcd(j, x), gcd(k, x)
                    g[gj][k] = (g[gj][k] + v) % mod
                    g[j][gk] = (g[j][gk] + v) % mod
            f = g
        return (sum(f[i][i] for i in range(m + 1)) - 1) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int subsequencePairCount(int[] nums) {
        final int MOD = 1_000_000_007;
        int m = 0;
        for (int x : nums) {
            m = Math.max(m, x);
        }
        int[][] f = new int[m + 1][m + 1];
        f[0][0] = 1;
        for (int x : nums) {
            int[][] g = new int[m + 1][m + 1];
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    int gj = gcd(j, x), gk = gcd(k, x);
                    g[gj][k] = (g[gj][k] + v) % MOD;
                    g[j][gk] = (g[j][gk] + v) % MOD;
                }
            }
            f = g;
        }
        long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (int) ((ans - 1 + MOD) % MOD);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int m = ranges::max(nums);
        vector f(m + 1, vector<int>(m + 1));
        f[0][0] = 1;
        for (int x : nums) {
            vector g(m + 1, vector<int>(m + 1));
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    int gj = gcd(j, x), gk = gcd(k, x);
                    g[gj][k] = (g[gj][k] + v) % MOD;
                    g[j][gk] = (g[j][gk] + v) % MOD;
                }
            }
            f.swap(g);
        }
        long long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (ans - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func subsequencePairCount(nums []int) int {
    const mod = 1_000_000_007
    m := slices.Max(nums)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    f[0][0] = 1
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range nums {
        g := make([][]int, m+1)
        for i := range g {
            g[i] = make([]int, m+1)
        }
        for j := 0; j <= m; j++ {
            for k := 0; k <= m; k++ {
                if f[j][k] == 0 {
                    continue
                }
                v := f[j][k]
                g[j][k] = (g[j][k] + v) % mod
                gj, gk := gcd(j, x), gcd(k, x)
                g[gj][k] = (g[gj][k] + v) % mod
                g[j][gk] = (g[j][gk] + v) % mod
            }
        }
        f = g
    }
    ans := 0
    for i := 0; i <= m; i++ {
        ans += f[i][i]
    }
    return (ans - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function subsequencePairCount(nums: number[]): number {
    const mod = 1_000_000_007;
    const m = Math.max(...nums);
    let f: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
    f[0][0] = 1;
    const gcd = (a: number, b: number): number => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    for (const x of nums) {
        const g: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
        for (let j = 0; j <= m; ++j) {
            for (let k = 0; k <= m; ++k) {
                if (f[j][k] === 0) {
                    continue;
                }
                const v = f[j][k];
                g[j][k] = (g[j][k] + v) % mod;
                const gj = gcd(j, x);
                const gk = gcd(k, x);
                g[gj][k] = (g[gj][k] + v) % mod;
                g[j][gk] = (g[j][gk] + v) % mod;
            }
        }
        f = g;
    }
    let ans = 0;
    for (let i = 0; i <= m; ++i) {
        ans += f[i][i];
    }
    return (((ans - 1) % mod) + mod) % mod;
}

Solution 2: Dynamic Programming

We can convert the memoization in Solution 1 into iterative dynamic programming.

Define \(f[j][k]\) as the number of ways where the current GCD of the first subsequence is \(j\) and that of the second subsequence is \(k\). Initially, \(f[0][0] = 1\).

Enumerate each element \(x\) in the array in order, and transfer using a new array \(g\):

  • Skip: \(g[j][k] \mathrel{+}= f[j][k]\);
  • Put into the first subsequence: \(g[\gcd(x, j)][k] \mathrel{+}= f[j][k]\);
  • Put into the second subsequence: \(g[j][\gcd(x, k)] \mathrel{+}= f[j][k]\).

After processing all elements, the answer is \(\sum_{i = 0}^{m} f[i][i] - 1\), taken modulo \(10^9 + 7\).

The time complexity is \(O(n \times m^2 \times \log m)\), and the space complexity is \(O(m^2)\), where \(n\) is the length of the array and \(m\) is the maximum value in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def subsequencePairCount(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        m = max(nums)
        f = [[0] * (m + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for x in nums:
            g = [[0] * (m + 1) for _ in range(m + 1)]
            for j in range(m + 1):
                for k in range(m + 1):
                    if f[j][k] == 0:
                        continue
                    v = f[j][k]
                    g[j][k] = (g[j][k] + v) % mod
                    g[gcd(x, j)][k] = (g[gcd(x, j)][k] + v) % mod
                    g[j][gcd(x, k)] = (g[j][gcd(x, k)] + v) % mod
            f = g
        return (sum(f[i][i] for i in range(m + 1)) - 1) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int subsequencePairCount(int[] nums) {
        final int MOD = 1_000_000_007;
        int m = 0;
        for (int x : nums) {
            m = Math.max(m, x);
        }
        int[][] f = new int[m + 1][m + 1];
        f[0][0] = 1;
        for (int x : nums) {
            int[][] g = new int[m + 1][m + 1];
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    int nj = gcd(x, j);
                    g[nj][k] = (g[nj][k] + v) % MOD;
                    int nk = gcd(x, k);
                    g[j][nk] = (g[j][nk] + v) % MOD;
                }
            }
            f = g;
        }
        long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (int) ((ans - 1 + MOD) % MOD);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int subsequencePairCount(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int m = ranges::max(nums);
        vector f(m + 1, vector<int>(m + 1));
        f[0][0] = 1;
        for (int x : nums) {
            vector g(m + 1, vector<int>(m + 1));
            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= m; ++k) {
                    if (f[j][k] == 0) {
                        continue;
                    }
                    int v = f[j][k];
                    g[j][k] = (g[j][k] + v) % MOD;
                    g[gcd(x, j)][k] = (g[gcd(x, j)][k] + v) % MOD;
                    g[j][gcd(x, k)] = (g[j][gcd(x, k)] + v) % MOD;
                }
            }
            f.swap(g);
        }
        long long ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans += f[i][i];
        }
        return (ans - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func subsequencePairCount(nums []int) int {
    const mod = 1_000_000_007
    m := slices.Max(nums)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, m+1)
    }
    f[0][0] = 1
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    for _, x := range nums {
        g := make([][]int, m+1)
        for i := range g {
            g[i] = make([]int, m+1)
        }
        for j := 0; j <= m; j++ {
            for k := 0; k <= m; k++ {
                if f[j][k] == 0 {
                    continue
                }
                v := f[j][k]
                g[j][k] = (g[j][k] + v) % mod
                nj := gcd(x, j)
                g[nj][k] = (g[nj][k] + v) % mod
                nk := gcd(x, k)
                g[j][nk] = (g[j][nk] + v) % mod
            }
        }
        f = g
    }
    ans := 0
    for i := 0; i <= m; i++ {
        ans += f[i][i]
    }
    return (ans - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function subsequencePairCount(nums: number[]): number {
    const mod = 1_000_000_007;
    const m = Math.max(...nums);
    let f: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
    f[0][0] = 1;
    const gcd = (a: number, b: number): number => {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    };
    for (const x of nums) {
        const g: number[][] = Array.from({ length: m + 1 }, () => Array(m + 1).fill(0));
        for (let j = 0; j <= m; ++j) {
            for (let k = 0; k <= m; ++k) {
                if (f[j][k] === 0) {
                    continue;
                }
                const v = f[j][k];
                g[j][k] = (g[j][k] + v) % mod;
                const nj = gcd(x, j);
                g[nj][k] = (g[nj][k] + v) % mod;
                const nk = gcd(x, k);
                g[j][nk] = (g[j][nk] + v) % mod;
            }
        }
        f = g;
    }
    let ans = 0;
    for (let i = 0; i <= m; ++i) {
        ans += f[i][i];
    }
    return (((ans - 1) % mod) + mod) % mod;
}

Comments