Skip to content

3336. Find the Number of Subsequences With Equal GCD 👍

Approach 1: Top-down

  • Time: $O(n \cdot \max(\texttt{nums})^2)$
  • Space: $O(n \cdot \max(\texttt{nums})^2)$
 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
class Solution {
 public:
  int subsequencePairCount(vector<int>& nums) {
    const int maxNum = ranges::max(nums);
    vector<vector<vector<int>>> mem(
        nums.size(),
        vector<vector<int>>(maxNum + 1, vector<int>(maxNum + 1, -1)));
    return subsequencePairCount(nums, 0, 0, 0, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of disjoint pairs `seq1` and `seq2` of nums[i..n - 1],
  // where GCD(seq1) == x and GCD(seq2) == y.
  int subsequencePairCount(const vector<int>& nums, int i, int x, int y,
                           vector<vector<vector<int>>>& mem) {
    if (i == nums.size())
      return x > 0 && x == y;
    if (mem[i][x][y] != -1)
      return mem[i][x][y];
    // 1. Skip nums[i].
    const int skip = subsequencePairCount(nums, i + 1, x, y, mem);
    // 2. Pick nums[i] in the first subsequence.
    const int take1 =
        subsequencePairCount(nums, i + 1, gcd(x, nums[i]), y, mem);
    // 3. Pick nums[i] in the second subsequence.
    const int take2 =
        subsequencePairCount(nums, i + 1, x, gcd(y, nums[i]), mem);
    return mem[i][x][y] = (static_cast<long>(skip) + take1 + take2) % kMod;
  }
};

 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
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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)

Approach 2: Bottom-up 2D DP

  • Time: $O(n \cdot \max(\texttt{nums})^2)$
  • Space: $O(n \cdot \max(\texttt{nums})^2)$
 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(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    const int maxNum = ranges::max(nums);
    // dp[i][x][y] := the number of disjoint pairs `seq1` and `seq2` of
    // nums[0..i - 1], where GCD(seq1) == x and GCD(seq2) == y
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(maxNum + 1, vector<int>(maxNum + 1)));
    dp[0][0][0] = 1;

    for (int i = 0; i < n; ++i)
      for (int x = 0; x <= maxNum; ++x)
        for (int y = 0; y <= maxNum; ++y) {
          // 1. Skip nums[i].
          dp[i + 1][x][y] += dp[i][x][y];
          dp[i + 1][x][y] %= kMod;
          // 2. Pick nums[i] in the first subsequence.
          const int newX = gcd(x, nums[i]);
          dp[i + 1][newX][y] += dp[i][x][y];
          dp[i + 1][newX][y] %= kMod;
          // 3. Pick nums[i] in the second subsequence.
          const int newY = gcd(y, nums[i]);
          dp[i + 1][x][newY] += dp[i][x][y];
          dp[i + 1][x][newY] %= kMod;
        }

    int ans = 0;
    for (int g = 1; g <= maxNum; ++g) {
      ans += dp[n][g][g];
      ans %= kMod;
    }
    return ans;
  }
};

 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
class Solution {
  public int subsequencePairCount(int[] nums) {
    final int MOD = 1_000_000_007;
    final int n = nums.length;
    final int maxNum = Arrays.stream(nums).max().getAsInt();
    // dp[i][x][y] := number of disjoint pairs `seq1` and `seq2` of
    // nums[0..i - 1], where GCD(seq1) == x and GCD(seq2) == y
    int[][][] dp = new int[n + 1][maxNum + 1][maxNum + 1];
    dp[0][0][0] = 1;

    for (int i = 0; i < n; ++i)
      for (int x = 0; x <= maxNum; ++x)
        for (int y = 0; y <= maxNum; ++y) {
          // 1. Skip nums[i].
          dp[i + 1][x][y] += dp[i][x][y];
          dp[i + 1][x][y] %= MOD;
          // 2. Pick nums[i] in the first subsequence.
          final int newX = gcd(x, nums[i]);
          dp[i + 1][newX][y] += dp[i][x][y];
          dp[i + 1][newX][y] %= MOD;
          // 3. Pick nums[i] in the second subsequence.
          final int newY = gcd(y, nums[i]);
          dp[i + 1][x][newY] += dp[i][x][y];
          dp[i + 1][x][newY] %= MOD;
        }

    int ans = 0;
    for (int g = 1; g <= maxNum; ++g) {
      ans += dp[n][g][g];
      ans %= MOD;
    }
    return ans;
  }

  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
class Solution:
  def subsequencePairCount(self, nums: list[int]) -> int:
    MOD = 1_000_000_007
    maxNum = max(nums)
    # dp[i][x][y] := number of disjoint pairs `seq1` and `seq2` of
    # nums[0..i - 1], where GCD(seq1) == x and GCD(seq2) == y
    dp = [[[0] * (maxNum + 1)
          for _ in range(maxNum + 1)]
          for _ in range(len(nums) + 1)]
    dp[0][0][0] = 1

    for i, num in enumerate(nums):
      for x in range(maxNum + 1):
        for y in range(maxNum + 1):
          # 1. Skip nums[i].
          dp[i + 1][x][y] += dp[i][x][y]
          dp[i + 1][x][y] %= MOD
          # 2. Pick nums[i] in the first subsequence.
          newX = math.gcd(x, num)
          dp[i + 1][newX][y] += dp[i][x][y]
          dp[i + 1][newX][y] %= MOD
          # 3. Pick nums[i] in the second subsequence.
          newY = math.gcd(y, num)
          dp[i + 1][x][newY] += dp[i][x][y]
          dp[i + 1][x][newY] %= MOD

    return sum(dp[-1][g][g]
               for g in range(1, maxNum + 1)) % MOD

Approach 3: Bottom-up 1D DP

  • Time: $O(n \cdot \max(\texttt{nums})^2)$
  • Space: $O(\max(\texttt{nums})^2)$
 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
class Solution {
 public:
  int subsequencePairCount(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    const int maxNum = ranges::max(nums);
    // dp[x][y] := the number of disjoint pairs `seq1` and `seq2` of
    // nums so far, where GCD(seq1) == x and GCD(seq2) == y
    vector<vector<int>> dp(maxNum + 1, vector<int>(maxNum + 1));
    dp[0][0] = 1;

    for (const int num : nums) {
      vector<vector<int>> newDp(maxNum + 1, vector<int>(maxNum + 1));
      for (int x = 0; x <= maxNum; ++x)
        for (int y = 0; y <= maxNum; ++y) {
          // 1. Skip `num`.
          newDp[x][y] += dp[x][y];
          newDp[x][y] %= kMod;
          // 2. Pick `num` in the first subsequence.
          const int newX = gcd(x, num);
          newDp[newX][y] += dp[x][y];
          newDp[newX][y] %= kMod;
          // 3. Pick `num` in the second subsequence.
          const int newY = gcd(y, num);
          newDp[x][newY] += dp[x][y];
          newDp[x][newY] %= kMod;
        }
      dp = std::move(newDp);
    }

    int ans = 0;
    for (int g = 1; g <= maxNum; ++g) {
      ans += dp[g][g];
      ans %= kMod;
    }
    return ans;
  }
};

 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
41
class Solution {
  public int subsequencePairCount(int[] nums) {
    final int MOD = 1_000_000_007;
    final int n = nums.length;
    final int maxNum = Arrays.stream(nums).max().getAsInt();
    // dp[x][y] := number of disjoint pairs `seq1` and `seq2` of
    // nums so far, where GCD(seq1) == x and GCD(seq2) == y
    int[][] dp = new int[maxNum + 1][maxNum + 1];
    dp[0][0] = 1;

    for (final int num : nums) {
      int[][] newDp = new int[maxNum + 1][maxNum + 1];
      for (int x = 0; x <= maxNum; ++x)
        for (int y = 0; y <= maxNum; ++y) {
          // 1. Skip `num`.
          newDp[x][y] += dp[x][y];
          newDp[x][y] %= MOD;
          // 2. Pick `num` in the first subsequence.
          final int newX = gcd(x, num);
          newDp[newX][y] += dp[x][y];
          newDp[newX][y] %= MOD;
          // 3. Pick `num` in the second subsequence.
          final int newY = gcd(y, num);
          newDp[x][newY] += dp[x][y];
          newDp[x][newY] %= MOD;
        }
      dp = newDp;
    }

    int ans = 0;
    for (int g = 1; g <= maxNum; ++g) {
      ans += dp[g][g];
      ans %= MOD;
    }
    return ans;
  }

  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
class Solution:
  def subsequencePairCount(self, nums: list[int]) -> int:
    MOD = 1_000_000_007
    maxNum = max(nums)
    # dp[x][y] := number of disjoint pairs `seq1` and `seq2` of
    # nums so far, where GCD(seq1) == x and GCD(seq2) == y
    dp = [[0] * (maxNum + 1) for _ in range(maxNum + 1)]
    dp[0][0] = 1

    for num in nums:
      newDp = [[0] * (maxNum + 1) for _ in range(maxNum + 1)]
      for x in range(maxNum + 1):
        for y in range(maxNum + 1):
          # 1. Skip `num`.
          newDp[x][y] += dp[x][y]
          newDp[x][y] %= MOD
          # 2. Pick `num` in the first subsequence.
          newX = math.gcd(x, num)
          newDp[newX][y] += dp[x][y]
          newDp[newX][y] %= MOD
          # 3. Pick `num` in the second subsequence.
          newY = math.gcd(y, num)
          newDp[x][newY] += dp[x][y]
          newDp[x][newY] %= MOD
      dp = newDp

    return sum(dp[g][g]
               for g in range(1, maxNum + 1)) % MOD