Compute distinct sums from limited coins

You are given two integer arrays, denom[0..n-1] and count[0..n-1], where denom[i] > 0 is a coin denomination and count[i] >= 0 is the number of available coins of that denomination. Return the number of distinct positive sums that can be formed using at most count[i] coins of value denom[i] (each coin is identical and can be used at most once). Describe your algorithm and analyze its time and space complexity. Discuss how you would handle large maximum reachable sums (e.g., up to 1e 6).

Compute Distinct Sums from Limited Coins

You are given two integer arrays, denom[0..n-1] and count[0..n-1], where denom[i] > 0 is a coin denomination and count[i] >= 0 is the number of available coins of that denomination. Coins of the same denomination are identical, and each coin may be used at most once (so you can use anywhere from 0 to count[i] coins of value denom[i]).

Return the number of distinct positive sums that can be formed. The empty selection produces a sum of 0 and is not counted.

Example: denom = [1, 5], count = [2, 1]. You have two 1-coins and one 5-coin. The achievable positive sums are {1, 2, 5, 6, 7}, so the answer is 5.

Follow-up to discuss aloud: how would you bound time and space when the maximum reachable sum is large (e.g. up to 1e6)? A boolean DP / bitset over reachable sums of size S = sum(denom[i] * count[i]) runs in O(total_coins * S) naively, or O(n * S) with a bounded-knapsack trick (sliding window per denomination); a bitset makes each denomination's update O(S / 64) per shift.

Constraints

• 1 <= n, but n may be 0 (empty arrays) -> answer 0
• denom[i] > 0
• count[i] >= 0 (a count of 0 contributes nothing)
• Coins of the same denomination are identical and order-independent
• Maximum reachable sum S can be large (e.g. up to 1e6); prefer a boolean array / bitset over a hash set at that scale

Hints

1. Model it as bounded subset-sum: maintain the set of all sums reachable so far, starting from {0}.
2. For each denomination d with c copies, a previously reachable sum b lets you newly reach b+d, b+2d, ..., b+c*d.
3. Process denominations one at a time so each coin of a given denomination is only added once per base — never re-feed sums created within the same denomination's expansion, or you'll exceed its count.
4. At scale (S up to 1e6), replace the hash set with a boolean array of size S+1 (or a 64-bit bitset) and use the classic bounded-knapsack sliding-window trick to keep it O(n*S).
5. Subtract 1 (drop the sum 0) at the end since only positive sums count.