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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: coins = [3,6,9], k = 3

Output: 9

Explanation: 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

1
2
3
4
5
6
7
8
9


Input: coins = [5,2], k = 7

Output: 12

Explanation: 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

Method 1 – Binary Search with Counting

Intuition

Since we can only use one denomination at a time, the possible amounts are all positive multiples of each coin. The set of all such amounts is the union of all sequences {coin, 2coin, 3coin, …}. To find the k-th smallest, we can use binary search on the answer and count how many such numbers are ≤ x.

Approach

  1. For a given x, the number of valid amounts ≤ x is the sum over all coins of x // coin.
  2. Use binary search for the smallest x such that the count is at least k.
  3. For each mid, compute the count as above.
  4. The answer is the smallest x for which the count is at least k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    long long kthSmallestAmount(vector<int>& coins, int k) {
        long long l = 1, r = 1e18, ans = -1;
        while (l <= r) {
            long long m = l + (r - l) / 2, cnt = 0;
            for (int c : coins) cnt += m / c;
            if (cnt >= k) { ans = m; r = m - 1; }
            else l = m + 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func kthSmallestAmount(coins []int, k int) int64 {
    l, r := int64(1), int64(1e18)
    var ans int64 = -1
    for l <= r {
        m := l + (r-l)/2
        cnt := int64(0)
        for _, c := range coins { cnt += m / int64(c) }
        if cnt >= int64(k) { ans = m; r = m - 1 } else { l = m + 1 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public long kthSmallestAmount(int[] coins, int k) {
        long l = 1, r = (long)1e18, ans = -1;
        while (l <= r) {
            long m = l + (r - l) / 2, cnt = 0;
            for (int c : coins) cnt += m / c;
            if (cnt >= k) { ans = m; r = m - 1; }
            else l = m + 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun kthSmallestAmount(coins: IntArray, k: Int): Long {
        var l = 1L
        var r = 1e18.toLong()
        var ans = -1L
        while (l <= r) {
            val m = l + (r - l) / 2
            var cnt = 0L
            for (c in coins) cnt += m / c
            if (cnt >= k) { ans = m; r = m - 1 } else { l = m + 1 }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def kthSmallestAmount(self, coins: list[int], k: int) -> int:
        l, r, ans = 1, 10**18, -1
        while l <= r:
            m = (l + r) // 2
            cnt = sum(m // c for c in coins)
            if cnt >= k:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn kth_smallest_amount(coins: Vec<i32>, k: i32) -> i64 {
        let (mut l, mut r, mut ans) = (1i64, 1e18 as i64, -1i64);
        while l <= r {
            let m = l + (r - l) / 2;
            let mut cnt = 0i64;
            for &c in &coins { cnt += m / c as i64; }
            if cnt >= k as i64 { ans = m; r = m - 1; } else { l = m + 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    kthSmallestAmount(coins: number[], k: number): number {
        let l = 1, r = 1e18, ans = -1;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            let cnt = 0n;
            for (const c of coins) cnt += BigInt(Math.floor(m / c));
            if (cnt >= BigInt(k)) { ans = m; r = m - 1; } else { l = m + 1; }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log M), where n is the number of coins and M is the answer range (up to 1e18). Each binary search step checks all coins.
  • 🧺 Space complexity: O(1), only a few variables are used.