#3404

Count Special Subsequences

medium · 29.8% accepted · 193 likes · top 7%

array · hash table · math · enumeration

⊣ practice⊣ open on leetcode ↗

Description

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