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
Find Kth Smallest Amount: coins=[3,5], k=4Input Coins:35Generate Amounts:Coin 3: 3, 6, 9, 12, 15...Coin 5: 5, 10, 15, 20...All Unique Amounts (sorted):3569101st2nd3rd4th5thAnswer: 4th smallest amount = 9
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
Asked in
Google 12 Meta 8
3.2K Views
Medium Frequency
~35 min Avg. Time
89 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen