Skip to content

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 > 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.

  • (p, q, r, s) = (0, 2, 4, 6):
    • This corresponds to elements (1, 3, 3, 1).
    • nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3
    • nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3

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):
    • This corresponds to elements (3, 3, 3, 3).
    • nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9
    • nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9
  • (p, q, r, s) = (1, 3, 5, 7):
    • This corresponds to elements (4, 4, 4, 4).
    • nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16
    • nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16
  • (p, q, r, s) = (0, 2, 5, 7):
    • This corresponds to elements (3, 3, 4, 4).
    • nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12
    • nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12

 

Constraints:

  • 7 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}

Comments