Minimum Number of Coins to be Added — Problem & Solution
Minimum Number of Coins to be Added solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Number of Coins to be Added is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array coins of coin values and an integer target.
An integer x is obtainable if some subset of the coins (each coin used at most once) sums to exactly x.
Return the minimum number of coins, of any values you like, that must be added to coins so that every integer in [1, target] is obtainable.
Example 1
Input: coins = [2,5], target = 10
Output: 2
Explanation: Add 1 and 4: with [1,2,4,5] every amount from 1 to 12 can be made. One extra coin is not enough — 1 is needed, and [1,2,5] cannot make 4.
Example 2
Input: coins = [1,4,10], target = 19
Output: 2
Explanation: Add 2 and 8.
Example 3
Input: coins = [1,1,1], target = 20
Output: 3
Explanation: Add 4, 8 and 16.
Constraints
1 <= target <= 10^51 <= coins.length <= 10^51 <= coins[i] <= target
Hints for Minimum Number of Coins to be Added
Hint 1
Suppose every amount in
[0, reach]is obtainable. A coin of valuec <= reach + 1extends that to[0, reach + c].Hint 2
Process the coins in increasing order. If the next coin is larger than
reach + 1, the amountreach + 1can never be made without help.Hint 3
When that happens, add a coin of value
reach + 1— it doubles the covered range, the most any single coin can do.
How to solve Minimum Number of Coins to be Added
Track the largest reach such that every amount 0..reach is obtainable. Coins are absorbed in increasing order; whenever the next coin leaves a gap at reach + 1, the best patch is a coin worth exactly reach + 1.
Approach
- Sort
coins; setreach = 0,added = 0,i = 0. - While
reach < target: ifi < nandcoins[i] <= reach + 1, setreach += coins[i]and advancei. - Otherwise add the coin
reach + 1:reach = 2 * reach + 1andadded += 1. - Return
added.
Why it works
If 0..reach is obtainable and c <= reach + 1, then c..c + reach is too, and the two ranges touch, so 0..reach + c is obtainable. If the smallest unused coin exceeds reach + 1, no subset can make reach + 1 — every coin used would be at most reach in total or exceed it — so some added coin must be <= reach + 1; choosing exactly reach + 1 extends the range furthest, so no other choice can need fewer additions.
Complexity
- Time —
O(n log n + log target) - Space —
O(1) beyond the sort
Pitfalls
- The gap test is
coin > reach + 1, notcoin > reach: a coin equal toreach + 1fills the gap itself. - Stop as soon as
reach >= target; leftover coins do not matter. - The same coin value may appear several times — each copy is used at most once and extends
reachseparately.
Reference solution
Python
from typing import List
def minimumAddedCoins(coins: List[int], target: int) -> int:
reach = 0 # every amount in 0..reach is obtainable
added = 0
i = 0
a = sorted(coins)
while reach < target:
if i < len(a) and a[i] <= reach + 1:
reach += a[i]
i += 1
else:
reach += reach + 1 # add a coin worth reach + 1
added += 1
return addedJava
public static int minimumAddedCoins(int[] coins, int target) {
int[] a = coins.clone();
Arrays.sort(a);
long reach = 0; // every amount in 0..reach is obtainable
int added = 0, i = 0;
while (reach < target) {
if (i < a.length && a[i] <= reach + 1) {
reach += a[i++];
} else {
reach += reach + 1; // add a coin worth reach + 1
added++;
}
}
return added;
}C++
int minimumAddedCoins(vector<int>& coins, int target) {
vector<int> a = coins;
sort(a.begin(), a.end());
long long reach = 0; // every amount in 0..reach is obtainable
int added = 0;
size_t i = 0;
while (reach < target) {
if (i < a.size() && a[i] <= reach + 1) {
reach += a[i++];
} else {
reach += reach + 1; // add a coin worth reach + 1
added++;
}
}
return added;
}JavaScript
var minimumAddedCoins = function(coins, target) {
var a = coins.slice().sort(function(x, y) { return x - y; });
var reach = 0, added = 0, i = 0; // every amount in 0..reach is obtainable
while (reach < target) {
if (i < a.length && a[i] <= reach + 1) {
reach += a[i++];
} else {
reach += reach + 1; // add a coin worth reach + 1
added++;
}
}
return added;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms