3404. Count Special Subsequences
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 > 1ands - r > 1.
Return the number of different special subsequences in nums.
Example 1:
Input: nums = [1,2,3,4,3,6,1]
Output: 1
Explanation:
There is one special subsequence in nums.
(p, q, r, s) = (0, 2, 4, 6):<ul> <li>This corresponds to elements <code>(1, 3, 3, 1)</code>.</li> <li><code>nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3</code></li> </ul> </li>
Example 2:
Input: nums = [3,4,3,4,3,4,3,4]
Output: 3
Explanation:
There are three special subsequences in nums.
(p, q, r, s) = (0, 2, 4, 6):<ul> <li>This corresponds to elements <code>(3, 3, 3, 3)</code>.</li> <li><code>nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9</code></li> </ul> </li> <li><code>(p, q, r, s) = (1, 3, 5, 7)</code>: <ul> <li>This corresponds to elements <code>(4, 4, 4, 4)</code>.</li> <li><code>nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16</code></li> <li><code>nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16</code></li> </ul> </li> <li><code>(p, q, r, s) = (0, 2, 5, 7)</code>: <ul> <li>This corresponds to elements <code>(3, 3, 4, 4)</code>.</li> <li><code>nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12</code></li> <li><code>nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12</code></li> </ul> </li>
Constraints:
7 <= nums.length <= 10001 <= nums[i] <= 1000
Solutions
Solution 1
Python3
class Solution:
def numberOfSubsequences(self, nums: List[int]) -> int:
n = len(nums)
cnt = defaultdict(int)
for r in range(4, n - 2):
c = nums[r]
for s in range(r + 2, n):
d = nums[s]
g = gcd(c, d)
cnt[(d // g, c // g)] += 1
ans = 0
for q in range(2, n - 4):
b = nums[q]
for p in range(q - 1):
a = nums[p]
g = gcd(a, b)
ans += cnt[(a // g, b // g)]
c = nums[q + 2]
for s in range(q + 4, n):
d = nums[s]
g = gcd(c, d)
cnt[(d // g, c // g)] -= 1
return ans
Java
class Solution {
public long numberOfSubsequences(int[] nums) {
int n = nums.length;
Map<Integer, Integer> cnt = new HashMap<>();
for (int r = 4; r < n - 2; ++r) {
int c = nums[r];
for (int s = r + 2; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt.merge(((d / g) << 12) | (c / g), 1, Integer::sum);
}
}
long ans = 0;
for (int q = 2; q < n - 4; ++q) {
int b = nums[q];
for (int p = 0; p < q - 1; ++p) {
int a = nums[p];
int g = gcd(a, b);
ans += cnt.getOrDefault(((a / g) << 12) | (b / g), 0);
}
int c = nums[q + 2];
for (int s = q + 4; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt.merge(((d / g) << 12) | (c / g), -1, Integer::sum);
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
C++
class Solution {
public:
long long numberOfSubsequences(vector<int>& nums) {
int n = nums.size();
unordered_map<int, int> cnt;
for (int r = 4; r < n - 2; ++r) {
int c = nums[r];
for (int s = r + 2; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt[((d / g) << 12) | (c / g)]++;
}
}
long long ans = 0;
for (int q = 2; q < n - 4; ++q) {
int b = nums[q];
for (int p = 0; p < q - 1; ++p) {
int a = nums[p];
int g = gcd(a, b);
ans += cnt[((a / g) << 12) | (b / g)];
}
int c = nums[q + 2];
for (int s = q + 4; s < n; ++s) {
int d = nums[s];
int g = gcd(c, d);
cnt[((d / g) << 12) | (c / g)]--;
}
}
return ans;
}
};
Go
func numberOfSubsequences(nums []int) (ans int64) {
n := len(nums)
cnt := make(map[int]int)
gcd := func(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
for r := 4; r < n-2; r++ {
c := nums[r]
for s := r + 2; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]++
}
}
for q := 2; q < n-4; q++ {
b := nums[q]
for p := 0; p < q-1; p++ {
a := nums[p]
g := gcd(a, b)
key := ((a / g) << 12) | (b / g)
ans += int64(cnt[key])
}
c := nums[q+2]
for s := q + 4; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]--
}
}
return
}
TypeScript
function numberOfSubsequences(nums: number[]): number {
const n = nums.length;
const cnt = new Map<number, number>();
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
for (let r = 4; r < n - 2; r++) {
const c = nums[r];
for (let s = r + 2; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) + 1);
}
}
let ans = 0;
for (let q = 2; q < n - 4; q++) {
const b = nums[q];
for (let p = 0; p < q - 1; p++) {
const a = nums[p];
const g = gcd(a, b);
const key = ((a / g) << 12) | (b / g);
ans += cnt.get(key) || 0;
}
const c = nums[q + 2];
for (let s = q + 4; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) - 1);
}
}
return ans;
}