How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Visa.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Visa during technical interviews.

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.

Input: ([1], [4])

Expected Output: 4

Explanation: Four 1-coins give sums {1,2,3,4} -> 4 distinct.

Input: ([], [])

Expected Output: 0

Explanation: No coins -> no positive sums.

Input: ([5], [0])

Expected Output: 0

Explanation: A denomination with count 0 contributes nothing.

Input: ([3, 3], [1, 1])

Expected Output: 2

Explanation: Duplicate denomination: effectively two 3-coins -> sums {3,6} -> 2 distinct.

Input: ([1, 2, 5], [3, 2, 1])

Expected Output: 12

Explanation: Three 1s, two 2s, one 5. Reachable positive sums are {1,2,3,4,5,6,7,8,9,10,11,12} -> 12 distinct.

Input: ([7], [3])

Expected Output: 3

Explanation: Three 7-coins give {7,14,21} -> 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.

Quick Overview

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.