Loading 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.
Example 1
Input: coins = [3,6,9], k = 3
Output: 9
Explanation: Coins 6 and 9 only add multiples already produced by 3, so the reachable amounts are 3, 6, 9, 12, ... The 3rd smallest is 9.
Example 2
Input: coins = [5,2], k = 7
Output: 12
Explanation: Reachable amounts (multiples of 5 or 2): 2, 4, 5, 6, 8, 10, 12, ... The 7th smallest is 12.
Example 3
Input: coins = [1], k = 5
Output: 5
Explanation: Coin 1 produces every positive integer, so the 5th smallest amount is 5.
The producible amounts are exactly the numbers divisible by at least one coin. That count is monotonic, so binary search the smallest value whose count reaches k, using inclusion-exclusion over coin subsets to count without enumerating.
Run checks all cases above. Submit evaluates all test cases.