Kth Smallest Amount With Single Denomination Combination - Video Solutions

Problem Overview: You are given several coin denominations. You can use only one denomination at a time but any number of coins of that type. Each denomination generates multiples (d, 2d, 3d...). The task is to find the kth smallest amount that appears in the union of all these multiples.

Approach 1: Min-Heap Approach for Multiples (O(k log n) time, O(n) space)

Treat every denomination as an infinite sorted sequence of multiples. Start by pushing the first multiple of each denomination into a min-heap. Repeatedly pop the smallest value, record it if it is not a duplicate, and push the next multiple of the same denomination. A hash set or last-seen value helps avoid counting duplicates when two denominations produce the same amount (for example 6 from 2×3 and 3×2). This approach mirrors merging k sorted lists. It works well when k is moderate, but performance degrades for very large k because you must explicitly generate values one by one.

Approach 2: Mathematical Counting with Binary Search (O(2^n log R) time, O(1) space)

The optimal strategy avoids generating values directly. Instead, binary search the answer x. For each candidate value, compute how many valid amounts are ≤ x. Every denomination contributes x / coin multiples, but overlaps occur when a number is divisible by multiple denominations. Use inclusion–exclusion with LCM to handle overlaps: add counts for single coins, subtract counts for pairs using their LCM, add for triples, and so on. Subsets can be enumerated efficiently using bit manipulation. LCM calculations rely on number theory concepts. Combine this counting function with binary search over the numeric range until the smallest value with at least k valid amounts is found.

The key insight: instead of generating the sequence, compute how many values fall below a threshold. Binary search converts the problem into repeated counting queries, which is dramatically faster when k can reach very large values.

Recommended for interviews: The heap method shows you recognize the problem as merging sorted sequences, which is a solid baseline. Interviewers typically expect the binary-search + inclusion–exclusion approach because it demonstrates stronger algorithmic thinking, familiarity with LCM/GCD math, and efficient counting techniques.