Kth Smallest Amount With Single Denomination Combination - Problem
You are given an integer array coins representing coins of different denominations and an integer k.
You have an infinite number of coins of each denomination. However, you are not allowed to combine coins of different denominations.
Return the kth smallest amount that can be made using these coins.
Input & Output
Example 1 — Basic Case
$
Input:
coins = [3,5], k = 4
›
Output:
9
💡 Note:
The amounts we can make are: 3, 5, 6, 9, 10, 12, 15, ... The 4th smallest is 9.
Example 2 — Single Coin
$
Input:
coins = [5], k = 2
›
Output:
10
💡 Note:
With only coin 5, we can make: 5, 10, 15, 20, ... The 2nd smallest is 10.
Example 3 — Common Multiples
$
Input:
coins = [2,4], k = 3
›
Output:
6
💡 Note:
Coin 2 makes: 2, 4, 6, 8, ... Coin 4 makes: 4, 8, 12, ... Combined unique amounts: 2, 4, 6, 8, ... The 3rd smallest is 6.
Constraints
- 1 ≤ coins.length ≤ 15
- 1 ≤ coins[i] ≤ 25
- 1 ≤ k ≤ 2 × 109
Visualization
Tap to expand
Understanding the Visualization
1
Input
Array of coin denominations and target k
2
Generate
Create amounts using each coin individually
3
Find Kth
Return the kth smallest unique amount
Key Takeaway
🎯 Key Insight: Use binary search on answer space with mathematical counting to efficiently find the kth smallest amount
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code