Minimum Number of Coins to be Added

Medium Arrays & Hashing Greedy Original on LeetCode

Reported atFlipkart

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^5
  • 1 <= coins.length <= 10^5
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(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.
SpaceO(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.

  1. can[0] = true; for every coin, update can[s] |= can[s - coin] for s from target down to coin.
  2. Find the smallest m in [1, target] with can[m] == false; if none, stop.
  3. 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;
        }
    }
}

2Optimal (sort + greedy reach)

TimeO(n log n + log target)Sorting dominates; every added coin at least doubles reach, so at most about log2(target) additions happen.
SpaceO(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.

  1. Sort coins; reach = 0, i = 0, added = 0.
  2. While reach < target: if i < n and coins[i] <= reach + 1, set reach += coins[i] and move i.
  3. Otherwise add the coin reach + 1: reach += reach + 1, added++.
  4. 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;
    }
}

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.