2952. Minimum Number of Coins to be Added
Problem Description
In this problem, you are given an array of integers coins
which represents different coin denominators and an integer target
. Your goal is to determine the smallest number of additional coins of any denomination that you must add to the coins
array so that it becomes possible to form every integer value in the inclusive range from 1 to target
.
This means that if you take any integer x
within the range [1, target]
, you should be able to choose a subsequence of coins from the updated coins
array that adds up exactly to x
. The term "subsequence" here refers to a sequence that can be derived from the coins
array by removing some or none of the coins, without changing the order of the remaining coins.
Intuition
The intuition behind the solution is using a greedy approach. The key idea is to always ensure that we can form all amounts leading up to the current target amount s
. Initially, we can form the amount 0
with no coins.
As we increment s
, we want to ensure that we can make all amounts up to the current s
. We sort the coins
to process them in ascending order. When we consider a new coin value, two scenarios can occur:
-
The coin value is less than or equal to
s
: In this case, by adding the coin to our collection, we can now form amounts in the range of[s, s+coin value - 1]
. This happens because we can already form all amounts up tos-1
, and with the new coin value, we extend the range by that coin value. -
The coin value is greater than
s
: If we encounter a coin with a value larger thans
, we cannot increments
using it, as there is a gap in the amounts we can form. To bridge this gap, we pretend to add a new coin of value exactlys
to our collection, which then allows us to form all amounts up to2*s - 1
. In practical terms, this means we increments
to2*s
(doubling it) and increase the count of additional coins needed (ans
).
We continue this process until s
exceeds target
. The variable ans
keeps track of the number of additional coins we are injecting into the collection to maintain the required sequence.
Solution Approach
The solution provided is a direct implementation of the greedy approach described earlier. Here's a step-by-step explanation of how the algorithm is applied:
-
Sorting the Coins: First, we sort the
coins
array in non-decreasing order. This is important because it allows us to process the coins from the smallest to the largest, which is crucial for the greedy approach.1coins.sort()
-
Initialization: We initialize two variables:
s
starting at1
representing the current target amount we can form, andans
starting at0
indicating the number of additional coins needed. We also have an indexi
starting at0
for iterating over thecoins
array.1s = 1 2ans = i = 0
-
Iterating Through the Coins:
1while s <= target:
We loop until
s
exceeds or equalstarget
. This is our stopping condition, ensuring we can create all amounts from 1 totarget
. -
Using existing coins if they are less than or equal to 's': Inside the loop, we check whether we are still within bounds of the
coins
array and whether the current coin is less than or equal to the current amounts
that we want to construct.1if i < len(coins) and coins[i] <= s: 2 s += coins[i] 3 i += 1
If so, we add the value of that coin to
s
, effectively merging it into our running total, and move to the next coin. -
Injecting Additional Coins: When we encounter a coin value greater than
s
(or run out of provided coins), it means we have a gap in the amounts we can create. We simulate adding an additional coin of values
to our collection.1else: 2 s <<= 1 3 ans += 1
The operation
s <<= 1
doubless
, and we increase theans
counter to account for the additional coin we've theoretically added.
By the time we exit the loop, ans
will hold the minimum number of additional coins required for making every amount up to target
obtainable. The final step is simply to return the ans
.
1return ans
Throughout the implementation, we are using basic list operations for sorting and indexing, with no need for complex data structures. The pattern used in this algorithm is inherently greedy as it always "fills the gap" with the smallest possible coin needed at each step while using existing coins whenever possible.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach.
Suppose we are given the array coins = [1, 2, 5]
and the target
value is 11
. We want to find the minimum number of additional coins that will enable us to make every integer value from 1
to 11
.
Following the solution approach:
-
Sorting the Coins: First, we sort the array
coins
, which in this example is already sorted as[1, 2, 5]
. -
Initialization: We set
s = 1
,ans = 0
, andi = 0
.s
is the current target amount we can form,ans
is the additional coins needed, andi
is the index for thecoins
array. -
Iterating Through the Coins: We start iterating through the array with the condition
while s <= target
:s = 1
andcoins[i] = 1
(sincei = 0
): We addcoins[i]
tos
, gettings = 2
, and incrementi
to1
.
-
Using existing coins if they are less than or equal to 's':
-
s = 2
andcoins[i] = 2
(sincei = 1
): We addcoins[i]
tos
, gettings = 4
, and incrementi
to2
. -
s = 4
andcoins[i] = 5
(sincei = 2
): Here,coins[i]
is greater thans
, which means we cannot use this coin directly to forms
. We proceed to the next step.
-
-
Injecting Additional Coins:
-
Since
coins[i]
is greater thans
, we add an additional coin of values
to the collection which in this steps = 4
, nows
becomes8
(s <<= 1
), and we incrementans
to1
. -
The loop continues,
s = 8 =< target
, buti
has exceeded the length of coins, so we consider it as encountering a coin greater thans
again, thus we doubles
to16
and incrementans
again to2
. -
Now
s = 16
which is greater thantarget
, so the loop terminates.
-
The final returned value of ans
is 2
, indicating that we need to add two additional coins of denominations that we need to decide (in this example, additional coins of denominations 4
and 8
would work) to be able to make every amount from 1
to 11
with the given coins
array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minimumAddedCoins(self, coins: List[int], target: int) -> int:
5 # Sort the given list of coins in ascending order
6 coins.sort()
7
8 # Initialize the current sum of coins to 1, as the smallest coin we can add
9 current_sum = 1
10
11 # Initialize the answer (the number of coins to add) and index counter for the coins list
12 additional_coins_count = 0
13 coin_index = 0
14
15 # Continue until the current sum reaches the target value
16 while current_sum <= target:
17
18 # If there are more coins to consider and the next coin is less than or
19 # equal to the current sum, it means we can include this coin without missing any value
20 if coin_index < len(coins) and coins[coin_index] <= current_sum:
21 current_sum += coins[coin_index] # Add the value of the current coin to the sum
22 coin_index += 1 # Move to the next coin
23
24 # If no appropriate coin is found, we have to add a new coin
25 else:
26 # We double the current sum because by adding a coin with a value equal to the current sum,
27 # we ensure that we can reach all the sums up to twice the current sum.
28 current_sum <<= 1
29
30 # Increment the answer as we decide to add a new coin
31 additional_coins_count += 1
32
33 # Return the total number of additional coins needed to make the target value
34 return additional_coins_count
35
1class Solution {
2 public int minimumAddedCoins(int[] coins, int target) {
3 // Sort the array of coins to start with the smallest denomination.
4 Arrays.sort(coins);
5
6 // Initialize variables:
7 // - 'ans' will hold the count of additional coins required.
8 // - 'currentSum' represents the current sum we can create with the existing coins.
9 // - 'i' is used to iterate through the coins array.
10 int ans = 0;
11 int currentSum = 1; // We start from 1 because we want to be able to create sums starting from 1 up to 'target'.
12
13 // Iterate while the current sum is less than or equal to the target sum.
14 while (currentSum <= target) {
15 // If there are still coins left, and the current coin's value is less than or equal to the current sum,
16 // we can use this coin to increase the current sum.
17 if (i < coins.length && coins[i] <= currentSum) {
18 currentSum += coins[i]; // Add the coin's value to the current sum.
19 i++; // Move on to the next coin.
20 } else {
21 // If there are no coins left that can be used, or the next coin's value is too large,
22 // double the current sum. This corresponds to adding a coin with value equal to the current sum.
23 currentSum <<= 1; // This is equivalent to 'currentSum = currentSum * 2'.
24 ans++; // Increment the count of additional coins needed.
25 }
26 }
27
28 // Return the total number of additional coins needed to create all sums from 1 up to the target.
29 return ans;
30 }
31}
32
1class Solution {
2public:
3 // Function to find the minimum number of additional coins needed to make up to the target amount.
4 int minimumAddedCoins(vector<int>& coins, int target) {
5 // Sort the coins in increasing order.
6 sort(coins.begin(), coins.end());
7
8 // Initialize answer (additional coins needed) to 0.
9 int additionalCoins = 0;
10
11 // Initialize current amount to 1 (the minimum amount we can make with additional coins).
12 int currentSum = 1;
13
14 // Initialize the index for iterating through the sorted coins vector.
15 int coinIndex = 0;
16
17 // Continue until the current amount is less than or equal to the target amount.
18 while (currentSum <= target) {
19 // If we have not used all coins and the current coin is less than or equal to current amount,
20 // we can use this coin to make the current amount.
21 if (coinIndex < coins.size() && coins[coinIndex] <= currentSum) {
22 currentSum += coins[coinIndex++]; // Use the coin and increment the coinIndex.
23 } else {
24 // Otherwise, we need to add a coin that is double the current amount
25 // because it's the smallest denomination not yet used.
26 currentSum <<= 1; // Doubling the current amount.
27 additionalCoins++; // Increment the count of additional coins needed.
28 }
29 }
30
31 // Return the total number of additional coins needed.
32 return additionalCoins;
33 }
34};
35
1function minimumAddedCoins(coins: number[], target: number): number {
2 // Sort the coins array in ascending order to process them from smallest to largest
3 coins.sort((a, b) => a - b);
4
5 let additionalCoins = 0; // Keep track of the number of additional coins needed
6 let currentSum = 1; // Initialize the current sum to 1, as 0 wouldn't be helpful for addition
7
8 // Iterate through the sorted coins array
9 // and simultaneously track the coverage of sums until we reach the target
10 for (let i = 0; currentSum <= target;) {
11 // If there are more coins to consider and the current coin is <= the current sum,
12 // add the coin's value to the sum and move to the next coin
13 if (i < coins.length && coins[i] <= currentSum) {
14 currentSum += coins[i++];
15 } else {
16 // If the current coin is bigger than the current sum,
17 // double the current sum (this is equivalent to adding a power-of-two coin)
18 // and increment the additionalCoins to indicate a new coin was added
19 currentSum <<= 1;
20 additionalCoins++;
21 }
22 }
23
24 // Return the final count of additional coins needed to reach the target sum
25 return additionalCoins;
26}
27
Time and Space Complexity
The time complexity of the code is primarily determined by the sorting operation and the while loop. The sort function has a complexity of O(n log n)
, where n
is the number of coins. After sorting, the while loop runs in O(n)
since it iterates over the sorted list of coins once. However, the s <<= 1
operation is logarithmic with respect to the target
, causing a O(log target)
complexity. Since there could be multiple doublings until s
exceeds target
, and considering the combined operations, the overall time complexity would be O(n log n + log target)
.
In terms of space complexity, the sort operation can be done in-place, which means the space used is constant with respect to the input. However, the source of additional space complexity is the internal implementation of the sort function which typically uses O(log n)
space on the call stack. Hence, the space complexity of the code is O(log n)
.
Please note that the reference answer mentions space complexity as O(log n)
which aligns with the typical space required for the sort's call stack in its internal implementation. However, if the sort were to be implemented in a way that is strictly in-place and without extra space usage (such as with an in-place variation of heapsort), the space complexity would be constant, O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.