Watch 7 video solutions for Minimum Number of Coins to be Added, a medium level problem involving Array, Greedy, Sorting. This walkthrough by Let's Practice Together has 3,296 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array coins, representing the values of the coins available, and an integer target.
An integer x is obtainable if there exists a subsequence of coins that sums to x.
Return the minimum number of coins of any value that need to be added to the array so that every integer in the range [1, target] is obtainable.
A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
Example 1:
Input: coins = [1,4,10], target = 19 Output: 2 Explanation: 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 Explanation: 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 Explanation: 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 <= 1051 <= coins.length <= 1051 <= coins[i] <= targetProblem Overview: You are given an array of coin values and a target. The goal is to ensure every value in the range [1, target] can be formed using the coins. You may add new coin denominations, and the task is to determine the minimum number of coins required to guarantee full coverage.
Approach 1: Brute Force Enumeration (Exponential Time, High Space)
A naive strategy tries adding different coin denominations and repeatedly checks whether every value from 1 to target can be constructed using subset sums of the available coins. This requires generating combinations or dynamic programming states for all possible sums. The search space grows exponentially as new coins are introduced. Time complexity is roughly O(2^n + target·n) depending on implementation, and space complexity can reach O(target). This approach mainly helps build intuition about why additional coins expand reachable sums but is not practical for large targets.
Approach 2: Greedy Coverage Expansion (O(n log n) time, O(1) space)
The optimal strategy uses a greedy observation. Suppose you can already form every value in the range [1, miss). The variable miss represents the smallest value you cannot currently form. If the next available coin value is ≤ miss, you can extend the reachable range by adding that coin, updating the coverage to [1, miss + coin). If the next coin is greater than miss, a gap exists. The only way to fill it optimally is to add a new coin with value miss. This doubles the reachable range to [1, 2·miss). Repeat until the coverage exceeds target.
The coins must be processed in sorted order, so the algorithm starts by sorting the array. Then iterate once through the coins while maintaining the current coverage boundary. Each step either consumes an existing coin or inserts a new one that maximally expands coverage. Sorting dominates the complexity, giving O(n log n) time and O(1) additional space.
This greedy method works because adding the smallest missing value always maximizes the new reachable interval while minimizing the number of added coins. The technique is closely related to the classic "patching array" problem and appears frequently in greedy design discussions.
Since the algorithm relies on processing coins in ascending order and extending coverage ranges, it also ties into concepts from sorting and sequential processing of an array.
Recommended for interviews: The greedy coverage approach is the expected solution. Interviewers want to see the insight that maintaining the smallest unreachable value (miss) allows you to decide whether to consume a coin or add one. Discussing brute force briefly shows problem exploration, but implementing the greedy strategy demonstrates algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | Exponential / O(2^n) | O(target) | Conceptual understanding of subset sums and coverage gaps |
| Greedy Coverage Expansion | O(n log n) | O(1) | Optimal solution when coins can be sorted and processed sequentially |