#2952

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Number of Coins to be Added

Determine the minimum number of coins to add so all values up to target are obtainable using a greedy sum approach.

Problem Statement

You are given a 0-indexed array coins representing available coin values and an integer target. A number x is obtainable if a subsequence of coins sums to x. Your task is to determine how to extend the array so that every integer from 1 to target can be obtained using the coins.

Return the minimum number of coins, of any positive integer value, that need to be added to the original array to make every integer in the range [1, target] obtainable. Consider the impact of missing intermediate sums and how greedy addition maintains coverage efficiently.

Examples

Example 1

Input: coins = [1,4,10], target = 19

Output: 2

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

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

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.

Constraints

1 <= target <= 105
1 <= coins.length <= 105
1 <= coins[i] <= target

Solution Approach

Sort and Initialize Reachable Sum

Sort the coins array and initialize a variable reachable = 1 representing the smallest sum that cannot yet be formed. Iterate through the coins to compare each coin with reachable.

Greedy Coin Addition

If the current coin is greater than reachable, add a new coin equal to reachable. This ensures the invariant that all sums less than reachable are obtainable. Increment reachable by the added coin and continue until reachable exceeds target.

Iterate Until Target Covered

Continue the process of either consuming the next coin or adding a new coin until reachable surpasses the target. Count each new coin addition to return the minimum number required to cover all sums up to target.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting plus O(n + m) for iteration, where n is the original array length and m is the number of coins added. Space complexity is O(1) beyond input storage since we track only reachable and counters.

What Interviewers Usually Probe

Ask if the candidate considers the smallest unobtainable sum first.
Check whether they attempt to add coins greedily to maintain the invariant.
Observe if they correctly handle coins larger than the current reachable sum.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the coins first and assuming any order works.
Skipping intermediate sums that require adding a coin, causing an incorrect minimum.
Overcomplicating with unnecessary DP when greedy sum tracking suffices.

Follow-up variants

Determine coins to remove so certain sums become unobtainable.
Compute the maximum sum reachable with a fixed number of additional coins.
Handle cases where coins have limited multiplicity instead of infinite use.

FAQ

What is the core pattern for Minimum Number of Coins to be Added?

The key pattern is greedy choice plus invariant validation, tracking the smallest sum that cannot yet be formed and adding coins to extend reach.

Do I need to consider all subsequences for sums?

No, by sorting and tracking the reachable sum, you can guarantee all sums are covered without enumerating all subsequences.

Can duplicate coin values affect the result?

Duplicates do not affect the minimal number of additional coins, as the greedy approach handles cumulative reachable sums correctly.

How does sorting help in this problem?

Sorting ensures coins are processed in increasing order, making it straightforward to check if the next coin extends the reachable range or requires adding a new coin.

What is a common mistake when solving this problem?

A frequent error is ignoring intermediate sums and adding coins in a non-greedy way, which can lead to adding more coins than necessary.

terminal

Solution

Solution 1: Greedy + Construction

Suppose the current amount we need to construct is $s$, and we have already constructed all amounts in $[0,...,s-1]$. If there is a new coin $x$, we add it to the array, which can construct all amounts in $[x, s+x-1]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        s = 1
        ans = i = 0
        while s <= target:
            if i < len(coins) and coins[i] <= s:
                s += coins[i]
                i += 1
            else:
                s <<= 1
                ans += 1
        return ans

Continue Practicing

#2966 divide array into arrays with max difference #2967 minimum cost to make array equalindromic #2971 find polygon with the largest perimeter