minimum-number-of-coins-to-be-added

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>coins</code>, representing the values of the coins available, and an integer <code>target</code>.

An integer <code>x</code> is obtainable if there exists a subsequence of <code>coins</code> that sums to <code>x</code>.

Return the minimum number of coins of any value that need to be added to the array so that every integer in the range <code>[1, target]</code> is obtainable.

A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.

&nbsp;
Example 1:

<pre>
Input: coins = [1,4,10], target = 19
Output: 2
Explanation: We need to add coins 2 and 8. The resulting array will be [1,2,4,8,10].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 2 is the minimum number of coins that need to be added to the array. 
</pre>

Example 2:

<pre>
Input: coins = [1,4,10,5,7,19], target = 19
Output: 1
Explanation: We only need to add the coin 2. The resulting array will be [1,2,4,5,7,10,19].
It can be shown that all integers from 1 to 19 are obtainable from the resulting array, and that 1 is the minimum number of coins that need to be added to the array. 
</pre>

Example 3:

<pre>
Input: coins = [1,1,1], target = 20
Output: 3
Explanation: We need to add coins 4, 8, and 16. The resulting array will be [1,1,1,4,8,16].
It can be shown that all integers from 1 to 20 are obtainable from the resulting array, and that 3 is the minimum number of coins that need to be added to the array.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= target &lt;= 105</code></li>
	<li><code>1 &lt;= coins.length &lt;= 105</code></li>
	<li><code>1 &lt;= coins[i] &lt;= target</code></li>
</ul>

minimumAddedCoins

Minimum Number of Coins to be Added

Coin Change

coin-change

零钱兑换

Most Expensive Item That Can Not Be Bought

most-expensive-item-that-can-not-be-bought

最贵的无法购买的商品

Greedy

Array

Sorting

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

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

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

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

&nbsp;

示例 1：

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

示例 2：

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

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= target &lt;= 105</code></li>
	<li><code>1 &lt;= coins.length &lt;= 105</code></li>
	<li><code>1 &lt;= coins[i] &lt;= target</code></li>
</ul>