3404. Count Special Subsequences

MediumArrayHash TableMathEnumeration

Problem 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, meaning: q - p > 1, r - q > 1, and s - r > 1.

The problem asks to return the number of different special subsequences in nums.

Intuition

To solve this problem, we need to identify subsequences of the array nums that conform to the specified conditions:

Multiplicative Condition: For indices (p, q, r, s), we require that nums[p] * nums[r] == nums[q] * nums[s]. This implies that the products must be equal for the specified indices.
Spacing Condition: Every pair of indices (p, q), (q, r), and (r, s) must have at least one element between them. Thus, q > p + 1, r > q + 1, and s > r + 1.

The solution involves iterating over potential indices (r, s) and maintaining a count of possible (p, q) indices that satisfy the condition for these (r, s) pairs using a dictionary. This count is updated as we progress through the array, allowing us to efficiently check the number of valid subsequences.

The algorithm involves:

Pre-processing for potential r and s indices and storing their characteristics in a count dictionary.
Iterating backward over potential (p, q) pairs, updating a running total of valid subsequences while adjusting the dictionary counts as q progresses.

This approach ensures that we efficiently count subsequences in adherence with both the multiplicative and spacing conditions.

Learn more about Math patterns.

Solution Approach

The solution to the problem uses a combination of iteration, dictionary data structure, and the concept of greatest common divisor (GCD) to efficiently count potential special subsequences:

Data Structures:
- A dictionary called cnt is used to keep track of tuples (d // g, c // g) for the pairs (r, s) where:
  - g is the greatest common divisor of nums[r] and nums[s].
  - This tuple effectively represents a reduced form of the ratio nums[s] / nums[r].
Iteration:
- First, iterate over potential r and s indices. Start with r = 4 and iterate while r < n - 2 to ensure the spacing condition that allows for future p and q. For each r, iterate over possible s values starting from r + 2 to satisfy the spacing requirement.
- For each valid (r, s), calculate the reduced form of nums[s] / nums[r] and update the cnt dictionary with this form as the key.
Counting Subsequences:
- Now, iterate over potential q indices from 2 and incrementally calculate valid (p, q) pairs.
- For each pair (p, q), compute the reduced form of nums[q] / nums[p] using GCD.
- Use this form to access cnt and compute the number of valid (r, s) pairs that could create a special subsequence with the current (p, q).
Adjust Dictionary:
- Move q after processing all p, and adjust the cnt by decreasing the count for tuples corresponding to q + 2.
Efficiency:
- This approach efficiently calculates potential subsequences by precomputing potential (r, s) pairs using the dictionary, then iterating over (p, q) pairs while maintaining spacing constraints. This reduces unnecessary recomputation and effectively uses the properties of GCD to handle multiplicative conditions.

By following this pattern of efficient calculation using dictionaries and GCD, the complex problem of counting subsequences is handled within a feasible computation time.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution using a simple example. Consider the array nums = [2, 3, 4, 6, 8, 12].

Initialization:
- We utilize a dictionary cnt to store counts of potential (r, s) pairs that satisfy nums[p] * nums[r] == nums[q] * nums[s] in reduced form.
Iterate over (r, s) pairs:
- Start with r = 4, and consider possible s values from r + 2 which means s = 6. However, s = 6 exceeds the array bounds, so instead evaluate r = 3 (s = 5).
- For pair (r, s) = (4, 5), calculate nums[s] / nums[r] = nums[5] / nums[4] = 12 / 8. The GCD of 12 and 8 is 4, so the reduced form is (3, 2). Update cnt[(3, 2)] = 1.
Iterate over (p, q) pairs:
- Consider q = 2, check potential p values: p = 0, since p < q.
- Calculate nums[q] / nums[p] = nums[2] / nums[0] = 4 / 2. The GCD of 4 and 2 is 2, so the reduced form is (2, 1). Look up cnt[(2, 1)] but find no matching (r, s).
- Move to q = 3, and calculate nums[q] / nums[p] = nums[3] / nums[0] = 6 / 2; GCD is 2, so the reduced form is (3, 1). Again, no match in cnt.
Adjust Counts:
- After processing each (p, q), adjust the cnt dictionary by decrementing counts related to q + 2 to maintain current state for future (p, q) pairs.

Using this method, examine every valid (p, q) pair, comparing the reduced product forms against precomputed (r, s) pair forms in cnt. Track the count of valid subsequences fulfilling both multiplicative and spacing conditions.

In this example, while no valid subsequences are found due to the lack of matching reduced forms, the walk-through covers essential details in understanding the solution methodology.

Solution Implementation

1from collections import defaultdict
2from math import gcd
3from typing import List
4
5class Solution:
6    def numberOfSubsequences(self, nums: List[int]) -> int:
7        n = len(nums)
8        # Dictionary to count pairs of reduced fractions (d//g, c//g)
9        pair_count = defaultdict(int)
10
11        # Traverse the list from index 4 to n-2 to form pairs and count them
12        for r in range(4, n - 2):
13            c = nums[r]
14            for s in range(r + 2, n):
15                d = nums[s]
16                # Calculate gcd of c and d
17                g = gcd(c, d)
18                # Increment the count of the reduced fraction (d//g, c//g)
19                pair_count[(d // g, c // g)] += 1
20
21        # Initialize the variable to store the number of valid subsequences
22        subsequence_count = 0
23
24        # Traverse the list from index 2 to n-4 to find subsequences
25        for q in range(2, n - 4):
26            b = nums[q]
27            # Iterate over pairs to check the condition
28            for p in range(q - 1):
29                a = nums[p]
30                # Calculate gcd of a and b
31                g = gcd(a, b)
32                # Add the number of corresponding pairs to the answer
33                subsequence_count += pair_count[(a // g, b // g)]
34
35            # Update the pair count by decrementing pairs that are no longer valid
36            c = nums[q + 2]
37            for s in range(q + 4, n):
38                d = nums[s]
39                # Calculate gcd of c and d
40                g = gcd(c, d)
41                # Decrement the count of the old pair
42                pair_count[(d // g, c // g)] -= 1
43
44        # Return the total count of valid subsequences
45        return subsequence_count
46

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public long numberOfSubsequences(int[] nums) {
6        int n = nums.length; // Length of the input array
7        Map<Integer, Integer> countMap = new HashMap<>(); // Map to store count of pairs
8
9        // Iterate over possible values for r, where 4 ≤ r < n - 2
10        for (int r = 4; r < n - 2; ++r) {
11            int currentC = nums[r]; // Value at index r
12            // Find possible pairs (c, d) such that r + 2 ≤ s < n
13            for (int s = r + 2; s < n; ++s) {
14                int currentD = nums[s]; // Value at index s
15                int gcdCD = gcd(currentC, currentD); // GCD of c and d
16                // Merge the reduced pair as a key in the map
17                countMap.merge(((currentD / gcdCD) << 12) | (currentC / gcdCD), 1, Integer::sum);
18            }
19        }
20
21        long ans = 0; // Initialize answer variable
22        // Iterate over possible values for q, where 2 ≤ q < n - 4
23        for (int q = 2; q < n - 4; ++q) {
24            int currentB = nums[q]; // Value at index q
25            // Check pairs (a, b) with 0 ≤ p < q - 1
26            for (int p = 0; p < q - 1; ++p) {
27                int currentA = nums[p]; // Value at index p
28                int gcdAB = gcd(currentA, currentB); // GCD of a and b
29                // Add to the number of subsequences if the pair exists in the map
30                ans += countMap.getOrDefault(((currentA / gcdAB) << 12) | (currentB / gcdAB), 0);
31            }
32
33            // Update map by removing pairs that are no longer needed
34            int currentC = nums[q + 2]; // Value at index q + 2
35            for (int s = q + 4; s < n; ++s) {
36                int currentD = nums[s]; // Value at index s
37                int gcdCD = gcd(currentC, currentD); // GCD of c and d
38                // Remove the reduced pair from the map
39                countMap.merge(((currentD / gcdCD) << 12) | (currentC / gcdCD), -1, Integer::sum);
40            }
41        }
42
43        return ans; // Return the total number of subsequences
44    }
45
46    private int gcd(int a, int b) {
47        // Recursive method to find Greatest Common Divisor using Euclidean algorithm
48        return b == 0 ? a : gcd(b, a % b);
49    }
50}
51

1#include <vector>
2#include <unordered_map>
3#include <numeric>
4
5class Solution {
6public:
7    long long numberOfSubsequences(std::vector<int>& nums) {
8        int n = nums.size();
9        std::unordered_map<int, int> cnt;
10
11        // Traverse through the array to count pairs (c, d) with gcd-based keys
12        for (int r = 4; r < n - 2; ++r) {
13            int c = nums[r];
14            for (int s = r + 2; s < n; ++s) {
15                int d = nums[s];
16                int g = std::gcd(c, d);
17                // Create a unique key based on the normalized pair (c/g, d/g)
18                cnt[((d / g) << 12) | (c / g)]++;
19            }
20        }
21
22        long long ans = 0;
23        // Iterate through the array looking for subsequences
24        for (int q = 2; q < n - 4; ++q) {
25            int b = nums[q];
26            for (int p = 0; p < q - 1; ++p) {
27                int a = nums[p];
28                int g = std::gcd(a, b);
29                // Lookup count of matching (a, b) pairs in cnt map
30                ans += cnt[((a / g) << 12) | (b / g)];
31            }
32            int c = nums[q + 2];
33            // Decrement counts for pairs no longer in range
34            for (int s = q + 4; s < n; ++s) {
35                int d = nums[s];
36                int g = std::gcd(c, d);
37                cnt[((d / g) << 12) | (c / g)]--;
38            }
39        }
40        return ans;
41    }
42};
43

1// Helper function to calculate the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.
2function gcd(a: number, b: number): number {
3    while (b !== 0) {
4        [a, b] = [b, a % b];
5    }
6    return a;
7}
8
9// Main function to calculate the number of specific subsequences in the given array.
10function numberOfSubsequences(nums: number[]): number {
11    const n = nums.length;
12    // Map to store the count of specific sequences using a key generated from the numbers.
13    const cnt = new Map<number, number>();
14
15    // Iterate through each possible r position with a gap of 2 from the end of the array.
16    for (let r = 4; r < n - 2; r++) {
17        const c = nums[r];
18        // For each chosen r, iterate s with a gap of 2 from r.
19        for (let s = r + 2; s < n; s++) {
20            const d = nums[s];
21            // Calculate gcd of c and d.
22            const g = gcd(c, d);
23            // Generate a unique key for storing in the map.
24            const key = ((d / g) << 12) | (c / g);
25            // Update the count map with the generated key.
26            cnt.set(key, (cnt.get(key) || 0) + 1);
27        }
28    }
29
30    let totalSubsequences = 0;
31
32    // Iterate through each possible q position with necessary gaps from both sides.
33    for (let q = 2; q < n - 4; q++) {
34        const b = nums[q];
35        // Iterate through each possible p preceding q with necessary spacing.
36        for (let p = 0; p < q - 1; p++) {
37            const a = nums[p];
38            // Calculate gcd of a and b.
39            const g = gcd(a, b);
40            // Generate the same unique key.
41            const key = ((a / g) << 12) | (b / g);
42            // Accumulate the count of valid subsequences found.
43            totalSubsequences += cnt.get(key) || 0;
44        }
45        // Update the map for future calculations by accounting for current `q` pair.
46        const c = nums[q + 2];
47        for (let s = q + 4; s < n; s++) {
48            const d = nums[s];
49            const g = gcd(c, d);
50            const key = ((d / g) << 12) | (c / g);
51            // Decrement the count in the map as this pair will no longer be valid for the following iterations.
52            cnt.set(key, (cnt.get(key) || 0) - 1);
53        }
54    }
55
56    return totalSubsequences;
57}
58

Time and Space Complexity

The code loops through the list nums multiple times using nested loops.

The first loop iterates r from 4 to n - 2 (inclusive). For each r, s iterates from r + 2 to n (exclusive).
- This results in approximately O(n^2) time complexity as a part of the loops, iterating through all possible pairs (c, d) after position r.
In the second loop, q iterates from 2 to n - 4 (inclusive). For each q:
- The p loop iterates from 0 to q - 1, and inside this loop, it checks subsequences against the cnt map. This part results in approximately O(n^2) time complexity due to potential full traversal.
- This is followed by another nested loop where s iterates from q + 4 to n. This contributes another O(n) time complexity considering this part involves modification of the cnt dictionary.

The time complexity overall can be estimated to be O(n^2) due to the nested iterations dominating the computations.

The space complexity is determined by the use of the cnt dictionary which stores ratios of numbers as keys. The space complexity is O(n) at most because it is used to store subsequence information across iterations, which is typically proportional to the number of elements being processed.

Therefore, overall:

Time complexity: O(n^2)
Space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: