3404. Count Special Subsequences LeetCode Solution
In this guide, you will get 3404. Count Special Subsequences LeetCode Solution with the best time and space complexity. The solution to Count Special Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 1, r – q > 1 and s – 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.
3404. Count Special Subsequences LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
3404. Count Special Subsequences LeetCode Solution in Java
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);
}
} // code provided by PROGIEZ
3404. Count Special Subsequences LeetCode Solution in Python
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 # code by PROGIEZ
