3404. Count Special Subsequences Medium

1/**
2 * [3404] Count Special Subsequences
3 *
4 * You are given an array nums consisting of positive integers.
5 * A special subsequence is defined as a <span data-keyword="subsequence-array">subsequence</span> of length 4, represented by indices (p, q, r, s), where p < q < r < s. This subsequence must satisfy the following conditions:
6 * 
7 * 	nums[p] * nums[r] == nums[q] * nums[s]
8 * 	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.
9 * 
10 * Return the number of different special subsequences in nums.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">nums = [1,2,3,4,3,6,1]</span>
15 * Output: <span class="example-io">1</span>
16 * Explanation:
17 * There is one special subsequence in nums.
18 * 
19 * 	(p, q, r, s) = (0, 2, 4, 6):
20 * 	
21 * 		This corresponds to elements (1, 3, 3, 1).
22 * 		nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3
23 * 		nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3
24 * 	
25 * 	
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">nums = [3,4,3,4,3,4,3,4]</span>
30 * Output: <span class="example-io">3</span>
31 * Explanation:
32 * There are three special subsequences in nums.
33 * 
34 * 	(p, q, r, s) = (0, 2, 4, 6):
35 * 	
36 * 		This corresponds to elements (3, 3, 3, 3).
37 * 		nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9
38 * 		nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9
39 * 	
40 * 	
41 * 	(p, q, r, s) = (1, 3, 5, 7):
42 * 	
43 * 		This corresponds to elements (4, 4, 4, 4).
44 * 		nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16
45 * 		nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16
46 * 	
47 * 	
48 * 	(p, q, r, s) = (0, 2, 5, 7):
49 * 	
50 * 		This corresponds to elements (3, 3, 4, 4).
51 * 		nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12
52 * 		nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12
53 * 	
54 * 	
55 * </div>
56 *  
57 * Constraints:
58 * 
59 * 	7 <= nums.length <= 1000
60 * 	1 <= nums[i] <= 1000
61 * 
62 */
63pub struct Solution {}
64
65// problem: https://leetcode.com/problems/count-special-subsequences/
66// discuss: https://leetcode.com/problems/count-special-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
67
68// submission codes start here
69
70impl Solution {
71    pub fn number_of_subsequences(nums: Vec<i32>) -> i64 {
72        
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_3404() {
84    }
85}
86