Skip to content

3404. Count Special Subsequences 👍

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

    // nums[p] * nums[r] == nums[q] * nums[s]
    // nums[p] / nums[q] == nums[s] / nums[r]
    for (int r = 4; r <= n - 1 - 2; ++r) {
      const int q = r - 2;
      for (int p = 0; p <= q - 2; ++p) {
        const int g = gcd(nums[p], nums[q]);
        ++count[nums[p] / g][nums[q] / g];
      }
      for (int s = r + 2; s < n; ++s) {
        const int g = gcd(nums[s], nums[r]);
        ans += count[nums[s] / g][nums[r] / g];
      }
    }

    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
class Solution {
  public long numberOfSubsequences(int[] nums) {
    final int n = nums.length;
    final int mx = Arrays.stream(nums).max().getAsInt();
    long ans = 0;
    int[][] count = new int[mx + 1][mx + 1];

    // nums[p] * nums[r] == nums[q] * nums[s]
    // nums[p] / nums[q] == nums[s] / nums[r]
    for (int r = 4; r <= n - 1 - 2; ++r) {
      final int q = r - 2;
      for (int p = 0; p <= q - 2; ++p) {
        final int g = gcd(nums[p], nums[q]);
        ++count[nums[p] / g][nums[q] / g];
      }
      for (int s = r + 2; s < n; ++s) {
        final int g = gcd(nums[s], nums[r]);
        ans += count[nums[s] / g][nums[r] / g];
      }
    }

    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
class Solution:
  def numberOfSubsequences(self, nums: list[int]) -> int:
    n = len(nums)
    mx = max(nums)
    ans = 0
    count = [[0] * (mx + 1) for _ in range(mx + 1)]

    # nums[p] * nums[r] == nums[q] * nums[s]
    # nums[p] / nums[q] == nums[s] / nums[r]
    for r in range(4, n - 1 - 2 + 1):
      q = r - 2
      for p in range(0, q - 2 + 1):
        g = math.gcd(nums[p], nums[q])
        count[nums[p] // g][nums[q] // g] += 1
      for s in range(r + 2, n):
        g = math.gcd(nums[s], nums[r])
        ans += count[nums[s] // g][nums[r] // g]

    return ans