Minimum Number of Coins to be Added
Minimum Number of Coins to be Added is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (sort + greedy reach), runs in O(n log n + log target) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (subset sums, add the smallest gap) up.
Problem
You are given an array coins of coin values and an integer target. A value x is obtainable if some subsequence of coins (each coin used at most once) adds up 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 the range [1, target] becomes obtainable.
Examples
Example 1
- Input
coins = [1, 5, 12], target = 25- Output
3- Why
- Adding 2 and 4 makes 1..7 obtainable; then 5 and 12 stretch that to 1..24. One more coin (for example another 1) is still needed to reach 25.
Example 2
- Input
coins = [8, 1, 4, 2], target = 15- Output
0- Why
- Powers of two 1, 2, 4, 8 already form every value from 1 to 15.
Example 3
- Input
coins = [3, 3, 3], target = 10- Output
2- Why
- Add 1 and 2 (covering 1..3); each 3 then extends the range by 3, up to 12.
Constraints
1 <= target <= 10^51 <= coins.length <= 10^51 <= coins[i] <= target
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (subset sums, add the smallest gap) | O(target · (n + a)) | O(target) |
| Optimal (sort + greedy reach) | O(n log n + log target) | O(1) |
1Brute force (subset sums, add the smallest gap)
O(target · (n + a))Each of the n original coins and the a added coins costs one O(target) pass of the table, plus a scan for the first gap after each addition.O(target)The boolean table of size target + 1.Track exactly which sums up to target can be formed with a subset-sum table. While some value in [1, target] is unreachable, add a coin equal to the smallest unreachable value (any useful coin must be at most that value, and the largest such choice covers the most), update the table, and count it.
can[0] = true; for every coin, updatecan[s] |= can[s - coin]forsfromtargetdown tocoin.- Find the smallest
min[1, target]withcan[m] == false; if none, stop. - Add a coin of value
m(same update), increment the answer and repeat.
class Solution {
public int minimumAddedCoins(int[] coins, int target) {
boolean[] can = new boolean[target + 1];
can[0] = true;
for (int c : coins) add(can, c);
int added = 0;
while (true) {
int missing = -1;
for (int s = 1; s <= target; s++) {
if (!can[s]) { missing = s; break; }
}
if (missing == -1) return added;
add(can, missing);
added++;
}
}
private void add(boolean[] can, int c) {
for (int s = can.length - 1; s >= c; s--) {
if (can[s - c]) can[s] = true;
}
}
}class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
can = [False] * (target + 1)
can[0] = True
def add(c: int) -> None:
for s in range(target, c - 1, -1):
if can[s - c]:
can[s] = True
for c in coins:
add(c)
added = 0
while True:
missing = next((s for s in range(1, target + 1) if not can[s]), -1)
if missing == -1:
return added
add(missing)
added += 1class Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
vector<bool> can(target + 1, false);
can[0] = true;
auto add = [&](int c) {
for (int s = target; s >= c; s--) {
if (can[s - c]) can[s] = true;
}
};
for (int c : coins) add(c);
int added = 0;
while (true) {
int missing = -1;
for (int s = 1; s <= target; s++) {
if (!can[s]) { missing = s; break; }
}
if (missing == -1) return added;
add(missing);
added++;
}
}
};function minimumAddedCoins(coins, target) {
const can = new Uint8Array(target + 1);
can[0] = 1;
const add = (c) => {
for (let s = target; s >= c; s--) {
if (can[s - c]) can[s] = 1;
}
};
for (const c of coins) add(c);
let added = 0;
while (true) {
let missing = -1;
for (let s = 1; s <= target; s++) {
if (!can[s]) { missing = s; break; }
}
if (missing === -1) return added;
add(missing);
added++;
}
}2Optimal (sort + greedy reach)
O(n log n + log target)Sorting dominates; every added coin at least doubles reach, so at most about log2(target) additions happen.O(1)Only a few counters besides the in-place sort.Sort the coins and keep reach, meaning every value in [1, reach] is obtainable. If the next coin c satisfies c <= reach + 1, it extends the range to [1, reach + c]. Otherwise reach + 1 can never be formed by the remaining (larger) coins, so we must add a coin; the largest useful value is reach + 1, which extends the range to [1, 2 · reach + 1]. Stop once reach >= target.
- Sort
coins;reach = 0,i = 0,added = 0. - While
reach < target: ifi < nandcoins[i] <= reach + 1, setreach += coins[i]and movei. - Otherwise add the coin
reach + 1:reach += reach + 1,added++. - Return
added.
class Solution {
public int minimumAddedCoins(int[] coins, int target) {
Arrays.sort(coins);
long reach = 0;
int i = 0, added = 0;
while (reach < target) {
if (i < coins.length && coins[i] <= reach + 1) {
reach += coins[i++];
} else {
reach += reach + 1;
added++;
}
}
return added;
}
}class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
coins.sort()
reach = 0
i = added = 0
while reach < target:
if i < len(coins) and coins[i] <= reach + 1:
reach += coins[i]
i += 1
else:
reach += reach + 1
added += 1
return addedclass Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
sort(coins.begin(), coins.end());
long long reach = 0;
int i = 0, added = 0;
while (reach < target) {
if (i < (int)coins.size() && coins[i] <= reach + 1) {
reach += coins[i++];
} else {
reach += reach + 1;
added++;
}
}
return added;
}
};function minimumAddedCoins(coins, target) {
coins.sort((a, b) => a - b);
let reach = 0, i = 0, added = 0;
while (reach < target) {
if (i < coins.length && coins[i] <= reach + 1) {
reach += coins[i++];
} else {
reach += reach + 1;
added++;
}
}
return added;
}Edge cases to test
- Coins already cover the whole range (answer 0)
- No coin of value 1, so 1 must be added first
- Duplicate coin values, which each extend the range
- A coin far larger than the current reachable range that only helps after several additions
- target = 1
Hints
Hint 1
Suppose every value from 1 to reach can be formed. Which new coin values keep the range gap-free?
Hint 2
A coin c <= reach + 1 extends the range to reach + c. A larger coin leaves reach + 1 unreachable.
Hint 3
Process the coins in increasing order. When the next coin is too big (or there is none), adding reach + 1 is the best possible addition: it doubles the range plus one.
FAQ
What is the best time complexity for Minimum Number of Coins to be Added?
Optimal (sort + greedy reach) runs in O(n log n + log target) time and O(1) extra space. Sorting dominates; every added coin at least doubles reach, so at most about log2(target) additions happen.
Which pattern does Minimum Number of Coins to be Added use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Minimum Number of Coins to be Added?
Yes. Brute force (subset sums, add the smallest gap) takes O(target · (n + a)) time and O(target) space. Track exactly which sums up to target can be formed with a subset-sum table.
Which edge cases should I test for Minimum Number of Coins to be Added?
Coins already cover the whole range (answer 0); No coin of value 1, so 1 must be added first; Duplicate coin values, which each extend the range; A coin far larger than the current reachable range that only helps after several additions; target = 1.