LeetCode 2952 - Minimum Number of Coins to be Added

The problem asks us to determine the minimum number of coins we need to add to an existing list of coins so that every integer from 1 to a given target can be formed as the sum of some subsequence of the coins.

leetcodemediumarraygreedysorting

LeetCode Problem 2952

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine the minimum number of coins we need to add to an existing list of coins so that every integer from 1 to a given target can be formed as the sum of some subsequence of the coins. Here, a subsequence is a selection of coins in their original order, but we can skip coins.

The input consists of a list coins where each element represents the value of a coin, and an integer target, which is the maximum sum we need to be able to form. The output is a single integer, representing the minimum number of additional coins needed to ensure that all integers from 1 to target can be formed.

Constraints indicate that the number of coins and the target value can be as large as 10^5, so brute-force approaches like trying all subsequences are infeasible. The coins are all positive integers, which guarantees that we can potentially cover the range by adding suitable coins.

Important edge cases include sequences where the smallest coin is greater than 1 (meaning we need a coin of value 1), sequences with repeated coins, and sequences that already allow all sums up to the target (requiring zero additional coins).

Approaches

The brute-force approach would attempt to compute all possible sums of subsequences of coins and check if each number from 1 to target is achievable. If a number is missing, we could try adding coins to fill gaps. This approach is correct in principle but exponentially slow, as the number of subsequences grows as 2^n, making it infeasible for large coins arrays.

The key observation for an optimal solution comes from a greedy approach inspired by the coin change coverage problem. If we maintain a variable miss representing the smallest value that cannot yet be formed, we can iterate through the sorted coins. If the current coin is less than or equal to miss, we can extend the range of obtainable sums; otherwise, we must add a coin of value miss to fill the gap. By repeating this process until miss > target, we guarantee that all numbers up to the target are obtainable.

This greedy approach works because it always extends the reachable sum range optimally: adding the smallest missing value ensures that no smaller numbers remain unreachable.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Generate all subsequence sums; infeasible for n up to 10^5
Optimal (Greedy) O(n log n) O(1) Sort coins and use miss tracking to add minimal coins

Algorithm Walkthrough

  1. Sort the coins in ascending order to consider smaller coins first. This ensures that we always try to use available coins to extend the reachable sum range before adding new coins.
  2. Initialize a variable miss = 1, representing the smallest sum we cannot yet form.
  3. Initialize a pointer i = 0 to iterate through the sorted coins and a counter added = 0 for the coins we need to add.
  4. Iterate while miss <= target:

a. If i < len(coins) and coins[i] <= miss, the current coin can extend the range of obtainable sums. We increase miss by coins[i] and move to the next coin (i += 1).

b. If i >= len(coins) or coins[i] > miss, it means the coin sequence cannot form miss, so we add a coin of value miss. Increment added and extend miss by itself (miss *= 2 in value accumulation terms). 5. Repeat until miss exceeds target. Return added as the minimum number of coins added.

Why it works: At each step, miss represents the smallest sum not yet achievable. By either using an existing coin or adding miss as a new coin, we guarantee that we cover all integers from 1 up to target with minimal additions. This greedy extension ensures no gaps are left in the achievable sums.

Python Solution

from typing import List

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

The code begins by sorting the coins. The miss variable tracks the smallest unobtainable value. For each coin that can extend the range, we add it to miss. If a coin cannot cover miss, we "add" a virtual coin of value miss and increment added. This continues until all sums up to target are covered.

Go Solution

import "sort"

func minimumAddedCoins(coins []int, target int) int {
    sort.Ints(coins)
    miss := 1
    added := 0
    i := 0
    n := len(coins)
    
    for miss <= target {
        if i < n && coins[i] <= miss {
            miss += coins[i]
            i++
        } else {
            miss += miss
            added++
        }
    }
    
    return added
}

In Go, we use sort.Ints to sort the coin array. The logic mirrors Python, with miss tracking the smallest unobtainable value and added counting the extra coins needed. We ensure proper index bounds checks for the slice.

Worked Examples

Example 1

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

Step miss coins[i] Action added
Start 1 1 use coin 1 0
miss = 2 4 4 > miss add 2 1
miss = 4 4 4 <= miss use coin 4 1
miss = 8 10 10 > miss add 8 2
miss = 16 10 10 <= miss use coin 10 2
miss = 26 > target - - terminate 2

Example 2

coins = [1,4,10,5,7,19], target = 19

After sorting: [1,4,5,7,10,19]

Add only coin 2 to cover the gap, so output = 1.

Example 3

coins = [1,1,1], target = 20

Add coins 4, 8, 16 in succession to cover gaps, so output = 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; iteration through coins is O(n)
Space O(1) Only a few integers used; no extra data structures

The algorithm scales efficiently for large coins arrays and targets up to 10^5.

Test Cases

# Provided examples
assert Solution().minimumAddedCoins([1,4,10], 19) == 2  # Example 1
assert Solution().minimumAddedCoins([1,4,10,5,7,19], 19) == 1  # Example 2
assert Solution().minimumAddedCoins([1,1,1], 20) == 3  # Example 3

# Edge cases
assert Solution().minimumAddedCoins([2,3], 5) == 1  # Need coin 1
assert Solution().minimumAddedCoins([1,2,3,4,5], 5) == 0  # Already covers all
assert Solution().minimumAddedCoins([5], 10) == 4  # Need coins 1,2,4
assert Solution().minimumAddedCoins([1], 1) == 0  # Single coin matches target
assert Solution().minimumAddedCoins([100], 50) == 1  # Need coin 1 since smallest coin > target
Test Why
[1,4,10], 19 Standard example with multiple additions
[1,4,10,5,7,19], 19 Only one coin needed
[1,1,1], 20 Requires powers-of-2 additions
[2,3], 5 Missing 1 triggers addition
[1,2,3,4,5], 5 Already complete range
[5], 10 Sparse coins requiring multiple additions
[1], 1 Minimal input
[100], 50 Small target vs large coin

Edge Cases

  1. Smallest coin greater than 1: If the first coin is larger than 1, we always need to add coin 1. The algorithm correctly identifies this by checking coins[i] <= miss and adding miss when necessary.
  2. Repeated coins: Multiple coins of the same value do not affect the algorithm adversely because each coin extends the obtainable sum in