Minimum Number of Coins to be Added

Medium
1444.

Minimum Number of Coins to be Added

Minimum Number of Coins to be Added is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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^5
  • 1 <= coins.length <= 10^5
  • 1 <= coins[i] <= target
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} coins
 * @param {number} target
 * @return {number}
 */
var minimumAddedCoins = function(coins, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Minimum Number of Coins to be Added

  1. Hint 1

    Suppose every amount in [0, reach] is obtainable. A coin of value c <= reach + 1 extends that to [0, reach + c].

  2. Hint 2

    Process the coins in increasing order. If the next coin is larger than reach + 1, the amount reach + 1 can never be made without help.

  3. 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

  1. Sort coins; set reach = 0, added = 0, i = 0.
  2. While reach < target: if i < n and coins[i] <= reach + 1, set reach += coins[i] and advance i.
  3. Otherwise add the coin reach + 1: reach = 2 * reach + 1 and added += 1.
  4. 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, not coin > reach: a coin equal to reach + 1 fills 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 reach separately.

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 added

Java

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