Find the least number of coins required that can make any change from 1 to 99 cents
Solution 1:
What you are looking for is Dynamic Programming.
You don't actually have to enumerate all the possible combinations for every possible values, because you can build it on top of previous answers.
You algorithm need to take 2 parameters:
- The list of possible coin values, here
[1, 5, 10, 25] - The range to cover, here
[1, 99]
And the goal is to compute the minimal set of coins required for this range.
The simplest way is to proceed in a bottom-up fashion:
Range Number of coins (in the minimal set)
1 5 10 25
[1,1] 1
[1,2] 2
[1,3] 3
[1,4] 4
[1,5] 5
[1,5]* 4 1 * two solutions here
[1,6] 4 1
[1,9] 4 1
[1,10] 5 1 * experience tells us it's not the most viable one :p
[1,10] 4 2 * not so viable either
[1,10] 4 1 1
[1,11] 4 1 1
[1,19] 4 1 1
[1,20] 5 1 1 * not viable (in the long run)
[1,20] 4 2 1 * not viable (in the long run)
[1,20] 4 1 2
It is somewhat easy, at each step we can proceed by adding at most one coin, we just need to know where. This boils down to the fact that the range [x,y] is included in [x,y+1] thus the minimal set for [x,y+1] should include the minimal set for [x,y].
As you may have noticed though, sometimes there are indecisions, ie multiple sets have the same number of coins. In this case, it can only be decided later on which one should be discarded.
It should be possible to improve its running time, when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for, I think.
For example, note that:
[1,5] 4*1 1*5
[1,9] 4*1 1*5
we add a nickel to cover [1,5] but this gives us up to [1,9] for free!
However, when dealing with outrageous input sets [2,3,5,10,25] to cover [2,99], I am unsure as how to check quickly the range covered by the new set, or it would be actually more efficient.
Solution 2:
You can very quickly find an upper bound.
Say, you take three quarters. Then you would only have to fill in the 'gaps' 1-24, 26-49, 51-74, 76-99 with other coins.
Trivially, that would work with 2 dimes, 1 nickel, and 4 pennies.
So, 3 + 4 + 2 + 1 should be an upper bound for your number of coins, Whenever your brute-force algorithm goes above thta, you can instantly stop searching any deeper.
The rest of the search should perform fast enough for any purpose with dynamic programming.
(edit: fixed answer as per Gabe's observation)
Solution 3:
You need at least 4 pennies, since you want to get 4 as a change, and you can do that only with pennies.
It isn't optimal to have more than 4 pennies. Instead of 4+x pennies, you can have 4 pennies and x nickels - they span at least the same range.
So you have exactly 4 pennies.
You need at least 1 nickel, since you want to get 5 as a change.
It isn't optimal to have more than 1 nickel. Instead of 1+x nickels, you can have 1 nickel and x dimes - they span at least the same range.
So you have exactly 1 nickel.
You need at least 2 dimes, since you want to get 20.
This means you have 4 pennies, 1 nickel and at least 2 dimes.
If you had less than 10 coins, you would have less than 3 quarters. But then the maximal possible change you could get using all coins is 4 + 5 + 20 + 50 = 79, not enough.
This means you have at least 10 coins. Thomas's answer shows that in fact if you have 4 pennies, 1 nickel, 2 dimes and 3 quarters, all is well.
Solution 4:
I've been learning about dynamic programming today, and here's the result:
coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])
# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
if cents in d.keys():
return d[cents]
elif cents > 0:
choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]
# given a list of tuples, python's min function
# uses the first element of each tuple for comparison
d[cents] = min(choices)
return d[cents]
else:
d[0] = (0, [])
return d[0]
for x in range(1, 100):
val = m(x)
print x, "cents requires", val[0], "coins:", val[1]
Dynamic programming really is magical.
Solution 5:
Nice Question. This is the logic I came up with. Tested with few scenarios including 25.
class Program
{
//Allowable denominations
const int penny = 1;
const int nickel = 5;
const int dime = 10;
const int quarter = 25;
const int maxCurrencyLevelForTest =55; //1-n where n<=99
static void Main(string[] args)
{
int minPenniesNeeded = 0;
int minNickelsNeeded = 0;
int minDimesNeeded = 0;
int minQuartersNeeded = 0;
if (maxCurrencyLevelForTest == penny)
{
minPenniesNeeded = 1;
}
else if (maxCurrencyLevelForTest < nickel)
{
minPenniesNeeded = MinCountNeeded(penny, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < dime)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, maxCurrencyLevelForTest);
}
else if (maxCurrencyLevelForTest < quarter)
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, maxCurrencyLevelForTest);
}
else
{
minPenniesNeeded = MinCountNeeded(penny, nickel - 1);
minNickelsNeeded = MinCountNeeded(nickel, dime - 1);
minDimesNeeded = MinCountNeeded(dime, quarter - 1);
var maxPossilbleValueWithoutQuarters = (minPenniesNeeded * penny + minNickelsNeeded * nickel + minDimesNeeded * dime);
if (maxCurrencyLevelForTest > maxPossilbleValueWithoutQuarters)
{
minQuartersNeeded = (((maxCurrencyLevelForTest - maxPossilbleValueWithoutQuarters)-1) / quarter) + 1;
}
}
var minCoinsNeeded = minPenniesNeeded + minNickelsNeeded+minDimesNeeded+minQuartersNeeded;
Console.WriteLine(String.Format("Min Number of coins needed: {0}", minCoinsNeeded));
Console.WriteLine(String.Format("Penny: {0} needed", minPenniesNeeded));
Console.WriteLine(String.Format("Nickels: {0} needed", minNickelsNeeded));
Console.WriteLine(String.Format("Dimes: {0} needed", minDimesNeeded));
Console.WriteLine(String.Format("Quarters: {0} needed", minQuartersNeeded));
Console.ReadLine();
}
private static int MinCountNeeded(int denomination, int upperRange)
{
int remainder;
return System.Math.DivRem(upperRange, denomination,out remainder);
}
}
Some results: When maxCurrencyLevelForTest = 25
Min Number of coins needed: 7
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 0 needed
When maxCurrencyLevelForTest = 99
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
maxCurrencyLevelForTest : 54
Min Number of coins needed: 8
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 1 needed
maxCurrencyLevelForTest : 55
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest : 79
Min Number of coins needed: 9
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 2 needed
maxCurrencyLevelForTest : 85
Min Number of coins needed: 10
Penny: 4 needed
Nickels: 1 needed
Dimes: 2 needed
Quarters: 3 needed
The code can further be refactored I guess.