Count special subsequences

Array Hash Table Math Enumeration

29.8% acceptance

Feb 25, 2026

193

You are given an array nums consisting of positive integers. A special subsequence is defined as a subsequence of length 4, represented by indices (p, q, r, s), where p < q < r < s. This subsequence must satisfy the following conditions: nums[p] * nums[r] == nums[q] * nums[s] There must be at least one element between each pair of indices. In other words, q - p > 1, r - q > 1 and s - r > 1. Return the number of different special subsequences in nums.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn number_of_subsequences(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    let mut ans = 0i64;

    // pq_count[(a,b)] = # of (p,q) pairs with q unlocked so far,
    // p <= q-2, where (nums[p]/g, nums[q]/g) = (a,b), g=gcd(nums[p],nums[q]).
    // Condition nums[p]*nums[r] == nums[q]*nums[s]
    // <=> nums[p]/nums[q] == nums[s]/nums[r]
    // <=> reduced ratio of (p,q) == reduced ratio of (s,r)
    let mut pq_count: HashMap<(i32, i32), i64> = HashMap::new();

    // Iterate r from 4 to n-1.
    // When r advances by 1, q = r-2 becomes newly valid; add all (p, q) pairs.
    for r in 4..n {
      let q = r - 2;
      // Add all pairs (p, q) with p in [0, q-2]
      for p in 0..q.saturating_sub(1) {
        let g = gcd(nums[p] as u32, nums[q] as u32) as i32;
        *pq_count.entry((nums[p] / g, nums[q] / g)).or_insert(0) += 1;
      }

      // For each s >= r+2, look up whether ratio (nums[s], nums[r]) matches any (p,q)
      for s in (r + 2)..n {
        let g = gcd(nums[r] as u32, nums[s] as u32) as i32;
        let key = (nums[s] / g, nums[r] / g);
        if let Some(&cnt) = pq_count.get(&key) {
          ans += cnt;
        }
      }
    }

    ans
  }
}

fn gcd(a: u32, b: u32) -> u32 {
  if b == 0 { a } else { gcd(b, a % b) }
}