Minimum Number of Coins to be Added - Solution & Explanation
Problem Statement
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] <= target
Approach Overview
Problem 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 1: Greedy Approach
This approach involves using a greedy algorithm to incrementally increase the range of obtainable values. Starting with an initial range that can be obtained from the original set of coins, we add the smallest unobtainable coin to extend this range. The goal is to keep extending the range until it includes all numbers up to the target.
This solution starts by sorting the array of coins. We then initialize a `current` variable to zero, which represents the maximum value we can obtain at each step. We iterate over the sorted coin array: if the current coin can extend our range (i.e., is less than or equal to `current` + 1), we add it to `current`. Otherwise, we add a new coin of value `current` + 1, extending our obtainable sum range effectively, and increase the count of new coins (`adds`) needed. We continue this until `current` is at least the target.
Complexity
Time Complexity: O(n log n) due to the sorting step, and space complexity: O(1) for the additional variables used.
Approach 2: 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].
Next, we discuss in two cases:
- If
x \le s, then we can merge the two intervals above to get all amounts in[0, s+x-1]. - If
x \gt s, then we need to add a coin with a face value ofs, so that we can construct all amounts in[0, 2s-1]. Then we consider the size relationship betweenxandsand continue to analyze.
Therefore, we sort the array coins in ascending order, and then traverse the coins in the array from small to large. For each coin x, we discuss in the above two cases until s > target.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n log n) due to the sorting step, and space complexity: O(1) for the additional variables used. |
| Greedy + Construction | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2952. Minimum Number of Coins to be Added | Weekly Contest 374 | Leetcode | Lets practice together • Let's Practice Together • 3,457 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Minimum Number of Coins to be Added easy or hard?
Minimum Number of Coins to be Added Python/Java solution
How to solve Minimum Number of Coins to be Added in O(n)?
What is the best approach for Minimum Number of Coins to be Added?
Is Minimum Number of Coins to be Added asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Coins to be Added?
What is the time complexity of Minimum Number of Coins to be Added?
Ready to solve this problem?
Practice Minimum Number of Coins to be Added with our built-in code editor and test cases.
Practice on FleetCode