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.

#3116

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

单面值组合的第 K 小金额

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。你有无限量的每种面额的硬币。但是，你不能组合使用不同面额的硬币。返回使用这些硬币能制造的第 k th 小金额。示例 1：输入： coins = [3,6,9], k = 3 输出： 9 解释：给定的硬币可以制造…

数组数学二分查找位运算组合数学

题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你不能组合使用不同面额的硬币。

返回使用这些硬币能制造的第 k^th 小金额。

示例 1：

输入： coins = [3,6,9], k = 3

输出： 9

解释：给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。

示例 2：

输入：coins = [5,2], k = 7

输出：12

解释：给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。

提示：

1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 10⁹
coins 包含两两不同的整数。

lightbulb

解题思路

方法一：二分查找 + 容斥原理

我们可以将题目转化为：找到最小的正整数 $x$ ，使得小于等于 $x$ 的且满足条件的数的个数恰好为 $k$ 个。如果 $x$ 满足条件，那么对任意 $x' > x$ 的 $x'$ 也满足条件，这存在单调性，因此我们可以使用二分查找，找到最小的满足条件的 $x$ 。

我们定义一个函数 check(x)，用来判断小于等于 $x$ 的且满足条件的数的个数是否大于等于 $k$ 。我们需要计算有多少个数可以由 $coins$ 中的数组合得到。

假设 $coins$ 为 $[a, b]$ ，根据容斥原理，小于等于 $x$ 的满足条件的数的个数为：

\left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor

如果 $coins$ 为 $[a, b, c]$ ，小于等于 $x$ 的满足条件的数的个数为：

\left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor + \left\lfloor \frac{x}{c} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor - \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor - \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor + \left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor

可以看到，我们需要累加所有任意奇数个数的情况，减去所有任意偶数个数的情况。

由于 $n \leq 15$ ，我们可以使用二进制枚举的方式，枚举所有的子集，计算满足条件的数的个数，我们记为 $cnt$ 。如果 $cnt \geq k$ ，那么我们需要找到最小的 $x$ ，使得 $check(x)$ 为真。

在二分查找开始时，我们定义二分查找的左边界 $l=1$ ，右边界 $r={10}^{11}$ ，然后我们不断地将中间值 $mid$ 代入 check 函数中，如果 check(mid) 为真，那么我们将右边界 $r$ 更新为 $mid$ ，否则我们将左边界 $l$ 更新为 $mid+1$ 。最终返回 $l$ 。

时间复杂度 $O(n \times 2^n \times \log (k \times M))$ ，其中 $n$ 是数组 $coins$ 的长度，而 $M$ 是数组 $coins$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        def check(mx: int) -> bool:
            cnt = 0
            for i in range(1, 1 << len(coins)):
                v = 1
                for j, x in enumerate(coins):
                    if i >> j & 1:
                        v = lcm(v, x)
                        if v > mx:
                            break
                m = i.bit_count()
                if m & 1:
                    cnt += mx // v
                else:
                    cnt -= mx // v
            return cnt >= k

        return bisect_left(range(10**11), True, key=check)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check whether you can count multiples without generating sequences explicitly.
question_mark
They may hint at binary searching over possible sums rather than coin indices.
question_mark
Expect questions about handling k up to 2 billion efficiently.

warning

常见陷阱

外企场景

error
Mistakenly combining different coin denominations in a sum, violating the problem constraints.
error
Generating all multiples up to k, causing memory overflow and slow execution.
error
Failing to handle duplicate sums correctly when different coins produce the same amount.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find kth largest amount instead of smallest using single-denomination multiples.
arrow_right_alt
Allow combining at most two denominations per sum while maintaining a large k.
arrow_right_alt
Restrict coin denominations to prime numbers only, testing counting efficiency.

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #3444 使数组包含目标值倍数的最少增量 #3539 魔法序列的数组乘积之和