#2952
Minimum Number of Coins to be Added
specialist · 760 · lc medium +31 · verified · 58% accepted · 432 likes · top 54%
Description
You have a 0-indexed array coins of coin values and an integer target. A value x is reachable if some subset of coins sums to x.
Add the fewest new coins (each of any denomination) so that every integer in [1, target] becomes reachable.
Return that minimum count.
Example 1:
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.
Example 2:
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.
Example 3:
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.
Code
1
2
3