Count all subsequences having product less than K

The problem, simply

You get a list of positive whole numbers arr and a number k. Pick any non-empty group of them (each position at most once). Multiply the group together. Count how many groups have a product strictly less than k.

Two groups are different if they use different positions, even if the numbers look the same.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build groups from left to right, as in the picture. From a group, try adding each later number. Count a group the moment it is made if its product is still below k.

1. Start with an empty group and product 1.
2. For each later number, multiply it in.
3. If the product is below k, count it and keep growing from there.
4. If not, do not grow it. All numbers are at least 1, so the product can only stay or grow.

class Solution {
    long count = 0;

    void grow(int[] arr, int start, long product, int k) {
        for (int i = start; i < arr.length; i++) {
            long p = product * arr[i];            // add arr[i] to the group
            if (p < k) {
                count++;                          // this group counts
                grow(arr, i + 1, p, k);           // try adding later numbers
            }                                     // else: too big, never grow it
        }
    }

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

How long it takes: with many small numbers (like lots of 1s), almost every group is valid, so it can visit all 2^n groups, O(2^n). Extra room: the chain of calls, O(n).

Way 2: the clever way

We never need to know which group it is, only its product. And only products from 1 to k - 1 matter. So keep cnt[p]: how many groups so far have product exactly p.

1. Start with all jars at 0.
2. For each number x, make a copy next of the jars (every group can skip x).
3. For every product p with cnt[p] > 0 and p * x < k, add cnt[p] to next[p * x] (those groups use x).
4. If x < k, add 1 to next[x] (the group with only x). Then cnt = next.
5. The answer is the sum of all jars.

class Solution {
    public long countSubsequences(int[] arr, int k) {
        if (k <= 1) return 0;                      // no product of positives is below 1
        long[] cnt = new long[k];                  // cnt[p]: groups with product exactly p
        for (int x : arr) {
            long[] next = cnt.clone();             // every old group may skip x
            for (int p = 1; p < k; p++) {
                if (cnt[p] > 0 && (long) p * x < k) {
                    next[p * x] += cnt[p];         // old groups that use x
                }
            }
            if (x < k) next[x]++;                  // the group with only x
            cnt = next;
        }
        long total = 0;
        for (int p = 1; p < k; p++) total += cnt[p];
        return total;
    }
}

How long it takes: n numbers, and for each we walk k jars, O(n * k). Extra room: two rows of k jars, O(k). This is fast when k is small (up to about a million). For a huge k, Way 1 with its early stops can be better.

Watch out for

• Use the copy next. If you update cnt in place while reading it, a group can use the same x twice. (Updating in place while walking p from high to low also works.)
• p * x can overflow an int when k is large. Multiply as long.
• If the list may contain 0, every group with a 0 has product 0, which is below any positive k. Count those separately.

What interviewers ask next

• Contiguous pieces only (subarrays)? Use a sliding window: grow the right end, and while the product is at least k, divide out the left end. Each right end adds right - left + 1. That is O(n).
• What if k is huge, like 10^9? Keep jars only for products that appear, in a hash map. Or count by "budget": ways(b, j) = ways(b, j-1) + 1 + ways(b / arr[j], j-1), where only about 2 * sqrt(b) different values of b / something exist.
• Sum less than k instead of product? Same idea with jars indexed by sum: that is the subset sum counting problem.
• Why must numbers be positive? With fractions or zeros, a big product can shrink later, so "never grow a too big group" stops being safe.

Remember this

Grown-up words: a group kept in order is a subsequence, the jars are a DP array indexed by product, the copy is a rolling array, and not growing a too big group is pruning.