Python - Count All Subsequences with Product Less Than K

Python – Count All Subsequences with Product Less Than K

This tutorial demonstrates how to count all subsequences of an array such that the product of their elements is less than a given integer K. We solve this problem using a dynamic programming approach with recursion and memoization. The solution is particularly useful for interviews where you need to discuss the thought process and optimize a brute-force solution.

Problem Statement

Given an array arr of positive integers and an integer K, count the number of non-empty subsequences whose product is less than K. A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements. If a subsequence’s product becomes equal to or exceeds K, it should not be counted.

Sample Input and Output

Example 1:

</>

Copy

# Input:
arr = [1, 2, 3]
K = 4

# Explanation:
# Valid subsequences and their products:
# [1]          -> 1 < 4
# [2]          -> 2 < 4
# [3]          -> 3 < 4
# [1, 2]       -> 1*2 = 2 < 4
# [1, 3]       -> 1*3 = 3 < 4
# [2, 3]       -> 2*3 = 6 (not valid, 6 ≥ 4)
# [1, 2, 3]    -> 1*2*3 = 6 (not valid, 6 ≥ 4)

# Total valid subsequences = 5

# Output:
5

Explanation: There are 5 valid non-empty subsequences from the array [1, 2, 3] whose product is less than 4. The subsequences [1], [2], [3], [1, 2], and [1, 3] satisfy the condition.

Example 2:

</>

Copy

# Input:
arr = [4, 5, 2]
K = 10

# Explanation:
# Valid subsequences and their products:
# [4]          -> 4 < 10
# [5]          -> 5 < 10
# [2]          -> 2 < 10
# [4, 5]       -> 4*5 = 20 (not valid)
# [4, 2]       -> 4*2 = 8 < 10
# [5, 2]       -> 5*2 = 10 (not valid, as it is not less than 10)
# [4, 5, 2]    -> 4*5*2 = 40 (not valid)

# Total valid subsequences = 4

# Output:
4

Explanation: In this example, there are 4 valid non-empty subsequences from the array [4, 5, 2] with product less than 10. These are [4], [5], [2], and [4, 2].

Solution Approach

We solve the problem using a recursive approach with memoization. The idea is to traverse the array and, at each index, decide whether to include the current element in the subsequence or skip it. While including an element, we update the current product and only continue if the product remains less than K.

The recursive function is defined as helper(i, prod), where i is the current index and prod is the product of the chosen elements so far. The function returns the count of valid subsequences starting from index i. We use a memoization dictionary to cache the results of subproblems to avoid redundant computations.

Python Program

</>

Copy

def count_subsequences(arr, K):
    """
    Count all non-empty subsequences of arr with product less than K.
    
    Parameters:
    arr (list): List of positive integers.
    K (int): The product threshold.
    
    Returns:
    int: The count of valid subsequences.
    """
    n = len(arr)
    memo = {}
    
    def helper(i, prod):
        # Base case: if we've processed all elements, no further subsequences can be formed.
        if i == n:
            return 0
        
        # Check memoized result
        if (i, prod) in memo:
            return memo[(i, prod)]
        
        count = 0
        # Decision: include arr[i] if it keeps product < K
        if prod * arr[i] < K:
            # Count the subsequence that starts with arr[i]
            count += 1
            # Also, count subsequences that include arr[i] along with later elements
            count += helper(i + 1, prod * arr[i])
        
        # Decision: skip arr[i] and try for later elements
        count += helper(i + 1, prod)
        
        memo[(i, prod)] = count
        return count
    
    return helper(0, 1)

# Test examples
print("Example 1 Output:", count_subsequences([1, 2, 3], 4))   # Expected output: 5
print("Example 2 Output:", count_subsequences([4, 5, 2], 10))    # Expected output: 4

Explanation: The function count_subsequences initiates a recursive helper function starting with a product of 1. For each element, it considers including it (if the new product remains less than K) or skipping it. Each valid inclusion adds 1 to the count (representing the subsequence that consists of just that element) plus the count of subsequences extended from that point. The memoization dictionary memo caches results for subproblems identified by the current index and product, ensuring that the same state is not recalculated multiple times.

Conclusion

In this tutorial, we tackled the problem of counting all non-empty subsequences whose product is less than a given value K using dynamic programming. The recursive approach with memoization efficiently explores the solution space while caching intermediate results to avoid redundant computations.

This method is particularly useful for interview settings, as it demonstrates problem decomposition, recursion, and optimization techniques.

TutorialKart

Python – Count All Subsequences with Product Less Than K