Use a binary search over the possible amounts and count how many multiples of each coin are below a candidate value. Incrementally adjust the search based on whether the candidate covers at least k sums. This efficiently identifies the exact kth smallest amount without generating all multiples explicitly, handling large k values with minimal computation.
Problem Statement
Given an array of distinct integers coins representing coin denominations and an integer k, find the kth smallest amount that can be formed using only one type of coin per sum. You cannot combine different denominations in a single sum, but each coin has infinite supply.
Return the kth smallest amount obtainable by these rules. For example, if coins = [3,6,9] and k = 3, the amounts are 3, 6, 9, 9, 12, 12, 15, 15, 18, and so on, counting repeated amounts only once per value. Identify the kth smallest in this sequence.
Examples
Example 1
Input: coins = [3,6,9], k = 3
Output: 9
The given coins can make the following amounts: Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc. Coin 6 produces multiples of 6: 6, 12, 18, 24, etc. Coin 9 produces multiples of 9: 9, 18, 27, 36, etc. All of the coins combined produce: 3, 6, 9 , 12, 15, etc.
Example 2
Input: coins = [5,2], k = 7
Output: 12
The given coins can make the following amounts: Coin 5 produces multiples of 5: 5, 10, 15, 20, etc. Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc. All of the coins combined produce: 2, 4, 5, 6, 8, 10, 12 , 14, 15, etc.
Constraints
- 1 <= coins.length <= 15
- 1 <= coins[i] <= 25
- 1 <= k <= 2 * 109
- coins contains pairwise distinct integers.
Solution Approach
Binary Search the Answer Space
Set low as the smallest coin and high as k times the largest coin. At each step, calculate mid and count how many amounts are <= mid by summing floor(mid / coin) for each coin. Adjust low or high until low meets high to locate the kth smallest amount.
Counting Multiples Efficiently
Instead of generating all multiples, compute how many multiples of each coin are less than or equal to a candidate mid. Summing these counts ensures we accurately determine whether mid reaches at least k sums, which is critical to the binary search pattern of this problem.
Handling Large k Values
Since k can be very large, directly storing all multiples is impractical. Using the counting approach with binary search avoids memory issues and reduces time complexity, fitting perfectly with this problem's single-denomination combination pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n log(k * maxCoin)) because each binary search step counts multiples for n coins. Space complexity is O(1) beyond input storage since no extra arrays are needed.
What Interviewers Usually Probe
- Check whether you can count multiples without generating sequences explicitly.
- They may hint at binary searching over possible sums rather than coin indices.
- Expect questions about handling k up to 2 billion efficiently.
Common Pitfalls or Variants
Common pitfalls
- Mistakenly combining different coin denominations in a sum, violating the problem constraints.
- Generating all multiples up to k, causing memory overflow and slow execution.
- Failing to handle duplicate sums correctly when different coins produce the same amount.
Follow-up variants
- Find kth largest amount instead of smallest using single-denomination multiples.
- Allow combining at most two denominations per sum while maintaining a large k.
- Restrict coin denominations to prime numbers only, testing counting efficiency.
How GhostInterview Helps
- Provides exact counting logic for multiples to support binary search decisions.
- Automatically handles edge cases like duplicate amounts and large k values.
- Visualizes the search over answer space, avoiding unnecessary sequence generation.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Kth Smallest Amount With Single Denomination Combination?
The main pattern is binary search over the valid answer space combined with counting multiples of each coin.
Can I combine different coin denominations in this problem?
No, each sum must use only a single coin denomination, with infinite supply per coin.
How do I handle very large k values efficiently?
Use binary search over the answer space and count multiples instead of generating all sums.
What is the time complexity of the solution?
Time complexity is O(n log(k * maxCoin)), iterating n coins for each binary search step.
How do I avoid counting duplicates incorrectly?
Count each multiple once per coin, and sum these counts without merging sequences to maintain correctness.
Need direct help with Kth Smallest Amount With Single Denomination Combination instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Kth Smallest Amount With Single Denomination Combination from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve the Sorted GCD Pair Queries problem by efficiently counting and locating GCDs of all array pairs using hash mapping.
Open problem page#3444 Minimum Increments for Target Multiples in an ArrayThis problem involves incrementing elements of an array to make sure each target element has at least one multiple in the array.
Open problem page#3539 Find Sum of Array Product of Magical SequencesUse state transition dynamic programming to count magical index sequences and accumulate weighted products without enumerating exponential orderings.
Open problem page