Count Special Subsequences

MEDIUM

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

Approaches

Checkout 3 different approaches to solve Count Special Subsequences. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward approach is to check every possible quadruplet of indices (p, q, r, s) to see if it forms a special subsequence. We can use four nested loops to generate all valid index combinations that satisfy p < q < r < s and the gap conditions q-p > 1, r-q > 1, s-r > 1. For each valid combination, we then check if the product equality nums[p] * nums[r] == nums[q] * nums[s] holds. If it does, we increment a counter.

Algorithm

Initialize a counter count to 0.
Use four nested loops to iterate through all possible combinations of indices (p, q, r, s).
To satisfy the gap conditions q-p > 1, r-q > 1, s-r > 1 directly, the loops can be set up as follows:
- p from 0 to n-7
- q from p+2 to n-5
- r from q+2 to n-3
- s from r+2 to n-1
Inside the innermost loop, check if the product condition nums[p] * nums[r] == nums[q] * nums[s] is met.
If the condition is true, increment the count.
After the loops complete, return count.

This method systematically explores all potential special subsequences. The four nested loops ensure that we consider every combination of four distinct indices (p, q, r, s) in increasing order. The loop bounds are carefully chosen to enforce the gap conditions. For example, q starts from p+2 to ensure q-p > 1. Similarly, r starts from q+2 and s from r+2. Inside the loops, we perform a simple multiplication and comparison. While simple to understand and implement, its performance is poor for larger inputs.

class Solution {
    public long countSpecialSubsequences(int[] nums) {
        int n = nums.length;
        long count = 0;
        for (int p = 0; p < n; p++) {
            for (int q = p + 2; q < n; q++) {
                for (int r = q + 2; r < n; r++) {
                    for (int s = r + 2; s < n; s++) {
                        if ((long) nums[p] * nums[r] == (long) nums[q] * nums[s]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N^4) - Four nested loops iterate through the array, where N is the length of `nums`. This is too slow for N=1000.Space Complexity: O(1) - We only use a few variables to store indices and the count.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Extremely inefficient due to four nested loops.
Will time out for the given constraints (N up to 1000).

Code Solutions

Checking out 3 solutions in different languages for Count Special Subsequences. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Special Subsequences

Patterns:

MathEnumeration

Data Structures:

ArrayHash Table