Compute distinct sums from limited coins
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Quick Answer: This question evaluates algorithmic problem-solving skills in combinatorics and resource-constrained subset-sum computation, focusing on dynamic programming, optimization, and complexity analysis within the Coding & Algorithms domain.
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
Examples
Input: ([1, 5], [2, 1])
Expected Output: 5
Explanation: Two 1-coins and one 5-coin. Positive sums: {1,2,5,6,7} -> 5 distinct.
Input: ([2, 3], [1, 1])
Expected Output: 3
Explanation: One 2 and one 3. Positive sums: {2,3,5} -> 3 distinct.
Hints
- Model it as bounded subset-sum: maintain the set of all sums reachable so far, starting from {0}.
- For each denomination d with c copies, a previously reachable sum b lets you newly reach b+d, b+2d, ..., b+c*d.
- 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.
- 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).
- Subtract 1 (drop the sum 0) at the end since only positive sums count.