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

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);
    }
}

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;
    }
};

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

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
}

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;
}

3404 - Count Special Subsequences

3404. Count Special Subsequences

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3404. Count Special Subsequences

Description

Solutions

Solution 1

All Problems

All Solutions