312. Count All Subsequences Having Product Less Than K

Given an array of n positive integers and an integer K, count the number of non-empty subsequences whose product of elements is strictly less than K.

Input: Three lines: n; n space-separated positive integers; the integer K. Output: Print a single integer - the count of non-empty subsequences whose product is strictly less than K.

1 <= n <= 100, 1 <= K <= 200

The bound on K (up to only 200) is precisely what makes this bucket-based technique both correct and efficient - a much larger K would require this approach to track an impractically large range of possible product values.

Count the non-empty subsequences of an array whose product of elements is strictly less than K. Brute force: Try every one of the 2^n possible subsequences directly, computing each one's product and checking against K - this is exponential, though the small constraint (n<=100) technically makes this borderline feasible; the DP approach is still far more efficient. Optimised: Tracking counts BY ACHIEVABLE PRODUCT VALUE (bounded by K, which is small - up to 200) rather than enumerating actual subsequences directly turns an exponential enumeration into a bounded, efficient bucket-update process - processing each element against a SNAPSHOT of the previous state ensures each element is only ever used ONCE per subsequence being counted.

Use the same product-bounded DP recurrence, but collapse the table to a single 1D array of size K indexed by product value, updating it in place for each element by iterating product values from high to low (so that an element isn't accidentally combined with itself twice within the same update step, the same care taken in 0/1-knapsack-style DPs). This keeps the exact same O(n*K) time as the 2D version but only ever needs one row's worth of memory instead of the full n*K table, since each element's update only depends on the previous state. Time: O(n*K) Space: O(K)

Since we only ever care whether a product stays strictly below K, and K is small, build a table dp[i][p] counting how many subsequences using the first i elements achieve product exactly p, for every p from 1 up to K-1 (any product that would reach or exceed K is simply not tracked further, since multiplying by values ≥ 1 can never bring it back down). Processing elements one at a time and, for each existing product p, either skip the element or extend to p * value[i] if that stays under K, fills the whole table in polynomial time - a huge improvement over enumerating every subsequence individually. Time: O(n*K) Space: O(n*K)

Recursively decide, for each of the n elements in order, whether to include it in the current subsequence or skip it, and once all elements have been decided, check whether the resulting product (if the subsequence is non-empty) is strictly less than K, counting it if so. This directly checks every one of the 2^n possible subsequences and is trivially correct by definition, but the exponential number of subsequences makes it infeasible once n grows past a couple dozen. Time: O(2^n) Space: O(n) recursion depth

1. Track, as a map or array indexed by ACHIEVABLE PRODUCT VALUE p (1<=p<K), how many subsequences seen so far (including the empty one, with product 1) achieve exactly that product. 2. Process one array element a at a time: for every EXISTING product p with p*a<K, add its count to the bucket for p*a - do this from a SNAPSHOT taken before processing a, so each element is used at most once per subsequence. 3. Sum every bucket's count at the end and subtract 1 to remove the empty subsequence (product 1, trivially always less than K).

Time: O(n * K) - for each of the n elements, updating up to K possible product buckets. Space: O(K), for the product-count buckets.

Test n = 1 (a single element, check whether it alone is below K) and K = 1 (no positive-integer product can be strictly less than 1, so the answer is 0).

Be ready to explain explicitly WHY a snapshot (not live in-place updates) is essential when processing each element - without it, a single element could be counted as contributing to a subsequence MULTIPLE times within the same processing step, over-counting.