Count all subsequences having product less than K

Problem Statement

Given an array of positive integers and a value k, count the number of non-empty subsequences whose product of elements is less than k.

Example:

• Input: arr = [1, 2, 3, 4], k = 10
• Output: 11 (subsequences: 1, 2, 3, 4, 2, 3, 4, 3, 3, 4, 4 — not 4=12, 4=12, etc.)

Noob-Friendly Explanation

Imagine you have items on a shelf, each with a number. You want to pick groups of items (at least one item) where if you multiply all their numbers together, the result is less than k. For [1, 2, 3, 4] with k=10: picking 3 gives product 6 (less than 10 ✓), but picking 4 gives product 12 (not less than 10 ✗). Count all the valid groups!

Approach 1: Brute Force (Recursion)

Intuition

Generate all possible non-empty subsequences. For each one, calculate the product and count it if the product is less than k.

Algorithm

1. For each element, include it or exclude it
2. Track the running product
3. If the product reaches or exceeds k, prune that branch
4. Count all valid non-empty subsequences

public class Solution {
    private int count;

    public int countSubsequences(int[] arr, int k) {
        count = 0;
        generate(arr, 0, 1, k);
        return count;
    }

    private void generate(int[] arr, int index, long product, int k) {
        if (index == arr.length) return;

        for (int i = index; i < arr.length; i++) {
            long newProduct = product * arr[i];

            if (newProduct < k) {
                count++; // this subsequence is valid
                generate(arr, i + 1, newProduct, k);
            }
            // If product >= k, no point extending (all elements are positive)
        }
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - In the worst case, we generate all subsequences
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Use a DP table where dp[i][j] represents the number of subsequences using the first i elements with product equal to j. For each element, we either skip it (keeping existing counts) or include it (multiplying product by the element).

Algorithm

1. Create dp[n+1][k] initialized to 0
2. For each element i and each product value j:
   • dp[i][j] += dp[i-1][j] (skip element i)
   • If j * arr[i-1] < k: dp[i][j * arr[i-1]] += dp[i-1][j] (include element i)
   • Also, if arr[i-1] < k: dp[i][arr[i-1]] += 1 (start a new subsequence with just this element)
3. Sum all values in the last row

Note: Since product values can be large, we cap at k (any product ≥ k is irrelevant).

public class Solution {
    public int countSubsequences(int[] arr, int k) {
        int n = arr.length;

        // dp[j] = number of subsequences with product j using elements so far
        // We only care about products < k
        int[] dp = new int[k];

        for (int i = 0; i < n; i++) {
            // Process in reverse to avoid counting same element twice
            int[] newDp = dp.clone();

            // Start a new subsequence with just arr[i]
            if (arr[i] < k) {
                newDp[arr[i]]++;
            }

            // Extend existing subsequences
            for (int j = 1; j < k; j++) {
                if (dp[j] > 0) {
                    long newProduct = (long) j * arr[i];
                    if (newProduct < k) {
                        newDp[(int) newProduct] += dp[j];
                    }
                }
            }

            dp = newDp;
        }

        // Count all subsequences (sum of all dp values)
        int total = 0;
        for (int j = 1; j < k; j++) {
            total += dp[j];
        }

        return total;
    }
}

Complexity Analysis

• Time Complexity: O(n * k) - For each of n elements, we iterate through products up to k
• Space Complexity: O(k) - 1D array of size k (optimized from 2D)