What is the core pattern for Minimum Number of Coins to be Added?

The key pattern is greedy choice plus invariant validation, tracking the smallest sum that cannot yet be formed and adding coins to extend reach.

Do I need to consider all subsequences for sums?

No, by sorting and tracking the reachable sum, you can guarantee all sums are covered without enumerating all subsequences.

Can duplicate coin values affect the result?

Duplicates do not affect the minimal number of additional coins, as the greedy approach handles cumulative reachable sums correctly.

How does sorting help in this problem?

Sorting ensures coins are processed in increasing order, making it straightforward to check if the next coin extends the reachable range or requires adding a new coin.

What is a common mistake when solving this problem?

A frequent error is ignoring intermediate sums and adding coins in a non-greedy way, which can lead to adding more coins than necessary.

#2952

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

需要添加的硬币的最小数量

给你一个下标从 0 开始的整数数组 coins ，表示可用的硬币的面值，以及一个整数 target 。如果存在某个 coins 的子序列总和为 x ，那么整数 x 就是一个可取得的金额。返回需要添加到数组中的任意面值硬币的最小数量，使范围 [1, target] 内的每个整数都属于 …

数组贪心排序

题目描述

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的非空数组，删除过程不会改变剩余元素的相对位置。

示例 1：

输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。

示例 2：

输入：coins = [1,4,10,5,7,19], target = 19
输出：1
解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19] 。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1 。

示例 3：

输入：coins = [1,1,1], target = 20
输出：3
解释：
需要添加面值为 4 、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16] 。 
可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3 。

提示：

1 <= target <= 10⁵
1 <= coins.length <= 10⁵
1 <= coins[i] <= target

lightbulb

解题思路

方法一：贪心 + 构造

我们不妨假设当前需要构造的金额为 $s$ ，且我们已经构造出了 $[0,...,s-1]$ 内的所有金额。如果此时有一个新的硬币 $x$ ，我们把它加入到数组中，可以构造出 $[x, s+x-1]$ 内的所有金额。

接下来，分类讨论：

如果 $x \le s$ ，那么我们可以将上面两个区间合并，得到 $[0, s+x-1]$ 内的所有金额。
如果 $x \gt s$ ，那么我们就需要添加一个面值为 $s$ 的硬币，这样可以构造出 $[0, 2s-1]$ 内的所有金额。然后我们再考虑 $x$ 和 $s$ 的大小关系，继续分析。

因此，我们将数组 $coins$ 按照升序排序，然后从小到大遍历数组中的硬币。对于每个硬币 $x$ ，我们进行上述分类讨论，直到 $s > target$ 为止。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        s = 1
        ans = i = 0
        while s <= target:
            if i < len(coins) and coins[i] <= s:
                s += coins[i]
                i += 1
            else:
                s <<= 1
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log n) for sorting plus O(n + m) for iteration, where n is the original array length and m is the number of coins added. Space complexity is O(1) beyond input storage since we track only reachable and counters.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask if the candidate considers the smallest unobtainable sum first.
question_mark
Check whether they attempt to add coins greedily to maintain the invariant.
question_mark
Observe if they correctly handle coins larger than the current reachable sum.

warning

常见陷阱

外企场景

error
Failing to sort the coins first and assuming any order works.
error
Skipping intermediate sums that require adding a coin, causing an incorrect minimum.
error
Overcomplicating with unnecessary DP when greedy sum tracking suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine coins to remove so certain sums become unobtainable.
arrow_right_alt
Compute the maximum sum reachable with a fixed number of additional coins.
arrow_right_alt
Handle cases where coins have limited multiplicity instead of infinite use.

help

常见问题

外企场景

继续练习

#2966 划分数组并满足最大差限制 #2967 使数组成为等数数组的最小代价 #2971 找到最大周长的多边形