Problem Description

You have an array coins containing integer values representing available coins, and an integer target. Your goal is to make every integer from 1 to target obtainable using subsequences of the coin array.

An integer x is considered obtainable if you can select some coins from the array (keeping their original order) that sum up to exactly x. You can use any coin at most once per subsequence.

The task is to find the minimum number of coins you need to add to the array so that every integer in the range [1, target] becomes obtainable. You can add coins of any value you choose.

For example, if you have coins [1, 4, 10] and target = 19:

• Initially, you can obtain: 1, 4, 5 (1+4), 10, 11 (1+10), 14 (4+10), 15 (1+4+10)
• You're missing values like 2, 3, 6, 7, 8, 9, 12, 13, 16, 17, 18, 19
• By strategically adding certain coins, you can fill these gaps

The problem uses a greedy approach where you maintain a range [0, s-1] of obtainable values. When you encounter or add a coin with value x:

• If x ≤ s, you can extend your obtainable range to [0, s+x-1]
• If x > s, there's a gap, and you need to add a coin with value s to double your range to [0, 2s-1]

The algorithm sorts the coins and processes them in order, adding new coins when necessary to ensure all values from 1 to target are obtainable.

Intuition

The key insight comes from thinking about what range of values we can create with our current coins. Let's start with a simple observation: if we can create all values from [0, s-1], what happens when we add a new coin with value x?

Consider this: if we already have ways to make 0, 1, 2, ..., s-1, and we get a coin worth x, then we can also make x, x+1, x+2, ..., x+(s-1) by combining the new coin with our existing combinations.

This creates two scenarios:

1. When x ≤ s: The ranges [0, s-1] and [x, x+s-1] overlap! They merge into one continuous range [0, x+s-1]. For instance, if we can make [0, 5] and add a coin worth 4, we can now make [0, 9].

2. When x > s: There's a gap! We can make [0, s-1] but the next coin helps us make [x, x+s-1]. The values from s to x-1 are unreachable.

The greedy strategy emerges from asking: "What's the best coin to add when we have a gap?" If we can currently make [0, s-1] and need to extend our range, adding a coin worth exactly s is optimal. Why? Because:

• It perfectly continues our range (no gap)
• It doubles our reachable range to [0, 2s-1]
• Any smaller coin would give us less extension
• Any larger coin would leave a gap

This leads to our algorithm: maintain the smallest unmakeable value s. Process coins in sorted order. If a coin is small enough (≤ s), use it to extend our range. If not, we must add coins worth s to fill the gap, doubling our range each time until we can use the current coin.

The sorting is crucial because processing smaller coins first maximizes how much we can build before needing to add new coins. It's like building a staircase - you want to use the smallest steps available before being forced to add your own steps.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a greedy construction strategy. We maintain a variable s representing the smallest value we cannot yet construct (initially 1), and build up our obtainable range incrementally.

Algorithm Steps:

1. Sort the coins array in ascending order. This ensures we process smaller coins first, maximizing the range we can build before adding new coins.

2. Initialize variables:

   • s = 1: The smallest value we're trying to make obtainable
   • ans = 0: Count of coins we need to add
   • i = 0: Index to traverse the sorted coins array

3. Main loop - Continue while s <= target:

   At each step, we've constructed all values in [0, s-1] and need to make s obtainable.

   • Case 1: Current coin is usable (i < len(coins) and coins[i] <= s):
     • The coin value is within our constructible range
     • Adding this coin extends our range from [0, s-1] to [0, s + coins[i] - 1]
     • Update: s += coins[i] and move to next coin i += 1
   • Case 2: Need to add a new coin (no usable coin or coins[i] > s):
     • There's a gap - we cannot make value s with existing coins
     • Optimally add a coin with value s to maximize range extension
     • This doubles our obtainable range from [0, s-1] to [0, 2s-1]
     • Update: s <<= 1 (equivalent to s *= 2) and increment ans += 1

4. Return ans - the minimum number of coins added.

Example Walkthrough:

Given coins = [1, 4, 10] and target = 19:

• Initially: s = 1, obtainable range is [0, 0] (empty)
• Process coin 1: 1 <= 1, so s = 1 + 1 = 2, range becomes [0, 1]
• Process coin 4: 4 > 2, need to add coin value 2, s = 4, ans = 1, range [0, 3]
• Process coin 4: 4 <= 4, so s = 4 + 4 = 8, range becomes [0, 7]
• Process coin 10: 10 > 8, need to add coin value 8, s = 16, ans = 2, range [0, 15]
• Process coin 10: 10 <= 16, so s = 16 + 10 = 26, range becomes [0, 25]
• Since 26 > 19, we're done. Return ans = 2.

The algorithm efficiently determines which coins to add by always choosing the value that maximizes the range extension while maintaining continuity.

Example Walkthrough

Let's walk through a smaller example to clearly illustrate the solution approach.

Given: coins = [1, 5, 10] and target = 20

We'll track our obtainable range at each step. Initially, we can make nothing, so our range is empty.

Step 1: Sort coins → [1, 5, 10]

• Initialize: s = 1 (smallest value we need to make), ans = 0 (coins added), i = 0 (index)
• Current obtainable range: [0, 0] (empty)

Step 2: Process first coin (value = 1)

• Check: Is coins[0] = 1 <= s = 1? Yes!
• Use this coin: extends range from [0, 0] to [0, 1]
• Update: s = 1 + 1 = 2, i = 1
• Now we can make: 0 (using no coins) and 1 (using coin 1)

Step 3: Try to make value 2

• Check: Is coins[1] = 5 <= s = 2? No! (5 > 2)
• Gap detected! We can't make 2, 3, or 4 with current coins
• Add a coin with value 2: ans = 1
• This doubles our range from [0, 1] to [0, 3]
• Update: s = 2 × 2 = 4
• Now we can make: 0, 1, 2, 3

Step 4: Try to make value 4

• Check: Is coins[1] = 5 <= s = 4? No! (5 > 4)
• Another gap! We can't make 4
• Add a coin with value 4: ans = 2
• This doubles our range from [0, 3] to [0, 7]
• Update: s = 4 × 2 = 8
• Now we can make: 0, 1, 2, 3, 4, 5, 6, 7

Step 5: Process second original coin (value = 5)

• Check: Is coins[1] = 5 <= s = 8? Yes!
• Use this coin: extends range from [0, 7] to [0, 12]
• Update: s = 8 + 5 = 13, i = 2
• Now we can make: 0 through 12

Step 6: Process third original coin (value = 10)

• Check: Is coins[2] = 10 <= s = 13? Yes!
• Use this coin: extends range from [0, 12] to [0, 22]
• Update: s = 13 + 10 = 23, i = 3
• Now we can make: 0 through 22

Step 7: Check termination

• Is s = 23 > target = 20? Yes!
• We can make all values from 1 to 20

Result: We need to add 2 coins (with values 2 and 4) to make all integers from 1 to 20 obtainable.

The key insight: when we encounter a gap (coin value > current s), we greedily add a coin with value exactly s to maximize our range extension. This ensures we fill gaps optimally while building toward our target.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the coins array. This complexity comes from two parts:

• Sorting the coins array takes O(n × log n) time
• The while loop iterates through each coin at most once and potentially adds coins when gaps exist. In the worst case, we need to add O(log target) coins (doubling each time), but since we process each original coin only once, the loop runs in O(n + log target) time
• Since log target is typically much smaller than n × log n from sorting, the overall time complexity is dominated by the sorting operation: O(n × log n)

The space complexity is O(log n). This comes from:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursion stack
• The algorithm itself only uses a constant amount of extra variables (s, ans, i), contributing O(1) additional space
• Therefore, the total space complexity is O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Sort the Coins Array

One of the most critical mistakes is forgetting to sort the coins array before processing. The greedy algorithm relies on processing coins in ascending order to build the obtainable range incrementally.

Incorrect Implementation:

def minimumAddedCoins(self, coins: List[int], target: int) -> int:
    # Missing coins.sort() - WRONG!
    max_reachable = 1
    added_coins = 0
    coin_index = 0
  
    while max_reachable <= target:
        if coin_index < len(coins) and coins[coin_index] <= max_reachable:
            max_reachable += coins[coin_index]
            coin_index += 1
        else:
            max_reachable <<= 1
            added_coins += 1
  
    return added_coins

Why it fails: Without sorting, you might encounter larger coins before smaller ones, causing unnecessary gaps and adding more coins than needed.

Example: For coins = [10, 1, 4] and target = 19, processing without sorting would add many unnecessary coins because we'd miss using coin 1 at the beginning.

2. Off-by-One Error in the Loop Condition

Another common mistake is using max_reachable < target instead of max_reachable <= target.

Incorrect Implementation:

while max_reachable < target:  # WRONG - misses when max_reachable equals target
    # ... rest of the logic

Why it fails: If max_reachable becomes exactly equal to target, we still need to check if we can actually form the value target. The loop should continue while we haven't covered all values up to and including target.

Example: For coins = [1] and target = 2, using < would stop when max_reachable = 2, but we haven't actually verified we can form value 2.

3. Incorrect Range Extension Logic

Some might incorrectly think that adding a coin with value x when the current range is [0, s-1] extends it to [0, s+x] instead of [0, s+x-1].

Incorrect Implementation:

if coin_index < len(coins) and coins[coin_index] <= max_reachable:
    max_reachable = max_reachable + coins[coin_index] + 1  # WRONG!
    coin_index += 1

Why it fails: This overcounts the obtainable range. When you can form values [0, s-1] and add a coin of value x, you can form [x, s+x-1], which combined with the original range gives [0, s+x-1], not [0, s+x].

4. Not Understanding When to Add a Coin

A subtle pitfall is misunderstanding the condition for when to add a new coin. Some might think we should add a coin whenever we encounter one that's too large, rather than understanding that we add a coin to fill gaps.

Incorrect Implementation:

while max_reachable <= target:
    if coin_index < len(coins):
        if coins[coin_index] <= max_reachable:
            max_reachable += coins[coin_index]
            coin_index += 1
        else:
            # WRONG: Always add when coin is too large, even if we don't need it
            max_reachable <<= 1
            added_coins += 1
            coin_index += 1  # WRONG: Skip the coin

Solution to All Pitfalls:

The correct implementation addresses all these issues:

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()  # Essential: Sort first
      
        max_reachable = 1  # Start with needing to form value 1
        added_coins = 0
        coin_index = 0
      
        # Continue while we haven't covered all values up to target
        while max_reachable <= target:
            # Check if current coin can help extend our range
            if coin_index < len(coins) and coins[coin_index] <= max_reachable:
                # Use the coin to extend range
                max_reachable += coins[coin_index]
                coin_index += 1
            else:
                # Add a coin with value max_reachable to maximize range extension
                max_reachable <<= 1  # Double the range
                added_coins += 1
                # Note: We don't increment coin_index here
      
        return added_coins

Key Points to Remember:

• Always sort the coins array first
• Use <= in the while condition, not <
• Understand that adding coin x to range [0, s-1] gives [0, s+x-1]
• Don't skip coins when adding new ones - revisit them after extending the range