Problem statement

You are given an array nums of positive integers.

A special subsequence is a choice of four indices (p, q, r, s) with p < q < r < s such that:

• nums[p] * nums[r] == nums[q] * nums[s], and
• consecutive indices are not neighbours: q - p > 1, r - q > 1 and s - r > 1.

Return the number of special subsequences in nums.

Example 1

Input: nums = [2,9,4,9,8,9,4]
Output: 1
Explanation: Only `(0, 2, 4, 6)` works: `2 * 8 = 16 = 4 * 4`.

Example 2

Input: nums = [1,1,1,1,1,1,1,1]
Output: 5
Explanation: Every product is 1, so each of the 5 ways to place four indices with gaps of at least 2 in 8 positions counts.

Example 3

Input: nums = [1,2,3,4,5,6,7]
Output: 0
Explanation: The only spaced choice is `(0, 2, 4, 6)`, and `1 * 5 != 3 * 7`.

Constraints

• 7 <= nums.length <= 200 (LeetCode allows 1000; reduced here so the count fits a 32-bit integer)
• 1 <= nums[i] <= 1000

Hints for Count Special Subsequences

1. Hint 1

   Rewrite the condition as a ratio: nums[p] / nums[q] == nums[s] / nums[r]. The left side only involves p, q; the right side only r, s.

2. Hint 2

   Fix r. Every valid q is at most r - 2, and every valid p at most q - 2. If you have already counted the ratios of all such (p, q) pairs, each s >= r + 2 just looks its ratio up.

3. Hint 3

   Store ratios exactly as reduced fractions (divide both parts by their gcd) — never as floating-point numbers. Moving r forward by one adds exactly the pairs with q = r - 2.

How to solve Count Special Subsequences

The equation separates into a ratio of the left pair and a ratio of the right pair. Sweeping the third index r from left to right, a hash map holds the reduced-fraction ratio of every (p, q) pair that can precede it, and every s to the right of r counts the matching pairs in one lookup.

Approach

1. Keep a map from a reduced fraction a/b to the number of pairs (p, q) with nums[p] / nums[q] = a/b seen so far.
2. For r from 4 to n - 3: let q = r - 2 and add the ratio nums[p] / nums[q] for every p <= q - 2 to the map.
3. Then, for every s from r + 2 to n - 1, add the map's count for the ratio nums[s] / nums[r] to the answer.
4. Reduce each fraction by its gcd and encode it as one integer key, e.g. a * 1024 + b (both parts are at most 1000).

Why it works

nums[p] * nums[r] = nums[q] * nums[s] is equivalent (all values positive) to nums[p] / nums[q] = nums[s] / nums[r], and two fractions are equal exactly when their reduced forms are identical. When the sweep reaches r, the map contains every pair with q <= r - 2 and p <= q - 2 — each added exactly once, at the step where its q equalled r - 2 — which is precisely the set of left pairs that may combine with this r. Each s >= r + 2 then counts its matches once, so every special subsequence is counted exactly once, at its own r.

Complexity

• Time — O(n^2 log V)
• Space — O(n^2) for the map in the worst case

Pitfalls

• Floating-point ratios can collide or miss: 1/3 computed two ways need not compare equal. Use reduced integer fractions.
• The gaps are strict: q - p > 1 means p <= q - 2, not p <= q - 1.
• On LeetCode's full limits the count overflows 32 bits and needs a 64-bit integer.

Reference solution

Python

from typing import List
from math import gcd

def numberOfSubsequences(nums: List[int]) -> int:
    n = len(nums)
    ratios = {}
    ans = 0
    for r in range(4, n - 2):
        q = r - 2
        b = nums[q]
        for p in range(q - 1):
            a = nums[p]
            g = gcd(a, b)
            key = (a // g) * 1024 + b // g
            ratios[key] = ratios.get(key, 0) + 1
        d = nums[r]
        for s in range(r + 2, n):
            c = nums[s]
            g = gcd(c, d)
            ans += ratios.get((c // g) * 1024 + d // g, 0)
    return ans

Java

static int gcdOf(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

public static int numberOfSubsequences(int[] nums) {
    int n = nums.length;
    HashMap<Integer, Integer> ratios = new HashMap<>();
    int ans = 0;
    for (int r = 4; r < n - 2; r++) {
        int q = r - 2, b = nums[q];
        for (int p = 0; p <= q - 2; p++) {
            int g = gcdOf(nums[p], b);
            ratios.merge((nums[p] / g) * 1024 + b / g, 1, Integer::sum);
        }
        int d = nums[r];
        for (int s = r + 2; s < n; s++) {
            int h = gcdOf(nums[s], d);
            ans += ratios.getOrDefault((nums[s] / h) * 1024 + d / h, 0);
        }
    }
    return ans;
}

C++

int numberOfSubsequences(vector<int>& nums) {
    int n = nums.size();
    unordered_map<int, int> ratios;
    int ans = 0;
    for (int r = 4; r < n - 2; r++) {
        int q = r - 2, b = nums[q];
        for (int p = 0; p <= q - 2; p++) {
            int g = __gcd(nums[p], b);
            ratios[(nums[p] / g) * 1024 + b / g]++;
        }
        int d = nums[r];
        for (int s = r + 2; s < n; s++) {
            int h = __gcd(nums[s], d);
            auto it = ratios.find((nums[s] / h) * 1024 + d / h);
            if (it != ratios.end()) ans += it->second;
        }
    }
    return ans;
}

JavaScript

var numberOfSubsequences = function(nums) {
    var n = nums.length;
    var ratios = new Map();
    var ans = 0;
    for (var r = 4; r < n - 2; r++) {
        var q = r - 2, b = nums[q];
        for (var p = 0; p <= q - 2; p++) {
            var g = gcdOf(nums[p], b);
            var key = (nums[p] / g) * 1024 + b / g;
            ratios.set(key, (ratios.get(key) || 0) + 1);
        }
        var d = nums[r];
        for (var s = r + 2; s < n; s++) {
            var h = gcdOf(nums[s], d);
            ans += ratios.get((nums[s] / h) * 1024 + d / h) || 0;
        }
    }
    return ans;
};

var gcdOf = function(a, b) {
    while (b) { var t = a % b; a = b; b = t; }
    return a;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium