[performance] Find the least number of coins required that can make any change from 1 to 99 cents

Recently I challenged my co-worker to write an algorithm to solve this problem:

Find the least number of coins required that can make any change from 1 to 99 cents. The coins can only be pennies (1), nickels (5), dimes (10), and quarters (25), and you must be able to make every value from 1 to 99 (in 1-cent increments) using those coins.

However, I realized that I don't actually know how to do this myself without examining every possible combination of coins. There has to be a better way of solving this problem, but I don't know what the generic name for this type of algorithm would be called, and I can't figure out a way to simplify it beyond looking at every solution.

I was wondering if anybody could point me in the right direction, or offer up an algorithm that's more efficient.

Solution with greedy approach in java is as below :

public class CoinChange {
    public static void main(String args[]) {
        int denominations[] = {1, 5, 10, 25};
        System.out.println("Total required coins are " + greeadApproach(53, denominations));
    }

    public static int greeadApproach(int amount, int denominations[]) {
        int cnt[] = new int[denominations.length];
        for (int i = denominations.length-1; amount > 0 && i >= 0; i--) {
            cnt[i] = (amount/denominations[i]);
            amount -= cnt[i] * denominations[i];            
        }
        int noOfCoins = 0;
        for (int cntVal : cnt) {
            noOfCoins+= cntVal;
        }
        return noOfCoins;
    }
}

But this works for single amount. If you want to run it for range, than we have to call it for each amount of range.

Example Program:

#include<stdio.h> 

    #define LEN 9 // array length
    int main(){
        int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count
        int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order}   
        int sum =0; //temp variable for sum
        int inc=0; // for loop
        int amount=0; // for total amount
        printf("Enter Amount :");
        scanf("%d",&amount);
        while(sum<amount){
            if((sum+cointypes[inc])<=amount){
                   sum = sum+  cointypes[inc];
                    //printf("%d[1] - %d\n",cointypes[inc],sum);
                    //switch case to count number of notes and coin
                   switch(cointypes[inc]){
                    case 1000:
                           coins[0]++;
                           break;
                    case 500:
                           coins[1]++;
                           break;
                    case 100:
                           coins[2]++;
                           break;
                    case 50:
                           coins[3]++;
                           break;               
                    case 20:
                           coins[4]++; 
                           break;
                    case 10:
                           coins[5]++;
                           break;
                    case 5:
                           coins[6]++;
                           break;
                    case 2:
                           coins[7]++;
                           break;
                    case 1:
                           coins[8]++;
                           break;
                       }
                }else{
                   inc++;
                }
            }
        printf("note for %d in\n note 1000 * %d\n note 500 * %d\n note 100 * %d\n note 50 * %d\n note 20 * %d\n note 10 * %d\n coin 5 * %d\n coin 2 * %d\n coin 1 * %d\n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]); 

    }

Assuming you're talking about US currency, you would want a Greedy Algorithm: http://en.wikipedia.org/wiki/Greedy_algorithm

In essence, you try all denominations from highest-to-lowest, taking as many coins as posible from each one until you've got nothing left.

For the general case see http://en.wikipedia.org/wiki/Change-making_problem, because you would want to use dynamic programming or linear programming to find the answer for arbitrary denominations where a greedy algorithm wouldn't work.

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.

On the one hand, this has been answered. On the other hand, most of the answers require many lines of code. This Python answer does not require many lines of code, merely many lines of thought ^_^ :

div_round_up = lambda a, b: a // b if a % b == 0 else a // b + 1

def optimum_change(*coins):
    wallet = [0 for i in range(0, len(coins) - 1)]
    for j in range(0, len(wallet)):
        target = coins[j + 1] - 1 
        target -= sum(wallet[i] * coins[i] for i in range(0, j))
        wallet[j] = max(0, div_round_up(target, coins[j]))
    return wallet

optimum_change(1, 5, 10, 25, 100)
#  [4, 1, 2, 3]

This is a very simple rescaling algorithm that may perhaps break for inputs which I haven't considered yet, but I think it should be robust. It basically says, "to add a new coin type to the wallet, peek at the next coin type N, then add the amount of new coins necessary to make target = N - 1." It calculates that you need at least ceil((target - wallet_value)/coin_value) to do so, and does not check if this will also make every number in between. Notice that the syntax encodes the "from 0 to 99 cents" by appending the final number "100" since that yields the appropriate final target.

The reason it does not check is something like, "if it can, it automatically will." Put more directly, once you do this step for a penny (value 1), the algorithm can "break" a nickel (value 5) into any subinterval 0 - 4. Once you do it for a nickel, the algorithm can now "break" a dime (value 10). And so on.

Of course, it does not require those particular inputs; you can use strange currencies too:

>>> optimum_change(1, 4, 7, 8, 100)
[3, 1, 0, 12]

Notice how it automatically ignores the 7 coin because it knows it can already "break" 8's with the change it has.

Came across this one today, while studying https://www.coursera.org/course/bioinformatics

DPCHANGE(money, coins)
 MinNumCoins(0) ? 0
 for m ? 1 to money
        MinNumCoins(m) ? 8
        for i ? 1 to |coins|
            if m = coini
                if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
                    MinNumCoins(m) ? MinNumCoins(m - coini) + 1
    output MinNumCoins(money)

Takes a comma-separated string of denominations available, and the target amount.

C# implementation:

    public static void DPCHANGE(int val, string denoms)
    {
        int[] idenoms = Array.ConvertAll(denoms.Split(','), int.Parse);
        Array.Sort(idenoms);
        int[] minNumCoins = new int[val + 1];

        minNumCoins[0] = 0;
        for (int m = 1; m <= val; m++)
        {
            minNumCoins[m] = Int32.MaxValue - 1;
            for (int i = 1; i <= idenoms.Count() - 1; i++)
            {
                if (m >= idenoms[i])
                {
                    if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m])
                    {
                        minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1;
                    }
                }
            }
        }
    }

This the code in c# to find the solution.

public struct CoinCount
{
    public int coinValue;
    public int noOfCoins;
}

/// <summary>
/// Find and returns the no of coins in each coins in coinSet
/// </summary>
/// <param name="coinSet">sorted coins value in assending order</param>
/// <returns></returns>
public CoinCount[] FindCoinsCountFor1to99Collection(int[] coinSet)
{
    // Add extra coin value 100 in the coin set. Since it need to find the collection upto 99.
    CoinCount[] result = new CoinCount[coinSet.Length];
    List<int> coinValues = new List<int>();
    coinValues.AddRange(coinSet);
    coinValues.Add(100);

    // Selected coin total values
    int totalCount = 0;
    for (int i = 0; i < coinValues.Count - 1; i++)
    {
        int count = 0;
        if (totalCount <= coinValues[i])
        {
            // Find the coins count
            int remainValue = coinValues[i + 1] - totalCount;
            count = (int)Math.Ceiling((remainValue * 1.0) / coinValues[i]);
        }
        else
        {
            if (totalCount <= coinValues[i + 1])
                count = 1;
            else
                count = 0;
        }
        result[i] = new CoinCount() { coinValue =  coinValues[i], noOfCoins = count };
        totalCount += coinValues[i] * count;
    }
    return result;
}

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class LeastNumofCoins 
{


    public int getNumofCoins(int amount)
        {
            int denominations[]={50,25,10,5,2,1};
            int numOfCoins=0;
            int index=0;
            while(amount>0)
            {
                int coin=denominations[index];
                 if(coin==amount)
                 {
                     numOfCoins++;
                     break;
                 }
                if(coin<=amount)
                    {
                        amount=amount-coin;
                        numOfCoins++;
                    }
                    else
                    {
                        index++;
                    }

            }
            return numOfCoins;
    }
    public static void main(String[] args) throws IOException 
    {

          Scanner scanner= new Scanner(new InputStreamReader(System.in));
          System.out.println("Enter the Amount:");
          int amoount=scanner.nextInt();
          System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount));
          scanner.close();
    }
}

Here's a simple version in Python.

#!/usr/bin/env python

required = []
coins = [25, 10, 5, 1]

t = []
for i in range(1, 100):
    while sum(t) != i:
        for c in coins:
            if sum(t) + c <= i:
                t.append(c)
                break
    for c in coins:
        while t.count(c) > required.count(c):
            required.append(c)
    del t[:]

print required

When run, it prints the following to stdout.

[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]

The code is pretty self-explanatory (thanks Python!), but basically the algorithm is to add the largest coin available that doesn't put you over the current total you're shooting for into your temporary list of coins (t in this case). Once you find the most efficient set of coins for a particular total, make sure there are at least that many of each coin in the required list. Do that for every total from 1 to 99 cents, and you're done.

After failing to find a good solution to this type of problem in PHP, I developed this function.

It takes any amount of money (up to $999.99) and returns an array of the minimum number of each bill / coin required to get to that value.

It first converts the value to an int in pennies (for some reason I would get errors at the very end when using standard float values).

The returned denominations are also in pennies (ie: 5000 = $50, 100 = $1, etc).

function makeChange($val)
{
    $amountOfMoney = intval($val*100);
    $cashInPennies = array(10000,5000,2000,1000,500,100,25,10,5,1);
    $outputArray = array();
    $currentSum = 0;
    $currentDenom = 0;

    while ($currentSum < $amountOfMoney) {
        if( ( $currentSum + $cashInPennies[$currentDenom] ) <= $amountOfMoney  ) {
            $currentSum = $currentSum + $cashInPennies[$currentDenom];
            $outputArray[$cashInPennies[$currentDenom]]++;
        } else {
            $currentDenom++;
        }
    }

    return $outputArray;

}

$change = 56.93;
$output = makeChange($change);

print_r($output);
echo "<br>Total number of bills & coins: ".array_sum($output);

=== OUTPUT ===

Array ( [5000] => 1 [500] => 1 [100] => 1 [25] => 3 [10] => 1 [5] => 1 [1] => 3 ) 
Total number of bills & coins: 11

Here's my take. One Interesting thing is that we need to check min coins needed to form up to coin_with_max_value(25 in our case) - 1 only. After that just calculate the sum of these min coins. From that point we just need to add certain number of coin_with_max_value, to form any number up to the total cost, depending on the difference of total cost and the sum found out. That's it.

So for values we have take, once min coins for 24 is found out: [1, 2, 2, 5, 10, 10]. We just need to keep adding a 25 coin for every 25 values exceeding 30(sum of min coins). Final answer for 99 is:
[1, 2, 2, 5, 10, 10, 25, 25, 25]
9

import itertools
import math


def ByCurrentCoins(val, coins):
  for i in range(1, len(coins) + 1):
    combinations = itertools.combinations(coins, i)
    for combination in combinations:
      if sum(combination) == val:
        return True

  return False

def ExtraCoin(val, all_coins, curr_coins):
  for c in all_coins:
    if ByCurrentCoins(val, curr_coins + [c]):
      return c

def main():
  cost = 99
  coins = sorted([1, 2, 5, 10, 25], reverse=True)
  max_coin = coins[0]

  curr_coins = []
  for c in range(1, min(max_coin, cost+1)):
    if ByCurrentCoins(c, curr_coins):
      continue

    extra_coin = ExtraCoin(c, coins, curr_coins)
    if not extra_coin:
      print -1
      return

    curr_coins.append(extra_coin)

  curr_sum = sum(curr_coins)
  if cost > curr_sum:
    extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
    curr_coins.extend([max_coin for _ in range(extra_max_coins)])

  print curr_coins
  print len(curr_coins)

Here goes my solution, again in Python and using dynamic programming. First I generate the minimum sequence of coins required for making change for each amount in the range 1..99, and from that result I find the maximum number of coins needed from each denomination:

def min_any_change():
    V, C = [1, 5, 10, 25], 99
    mxP, mxN, mxD, mxQ = 0, 0, 0, 0
    solution = min_change_table(V, C)
    for i in xrange(1, C+1):
        cP, cN, cD, cQ = 0, 0, 0, 0
        while i:
            coin = V[solution[i]]
            if coin == 1:
                cP += 1
            elif coin == 5:
                cN += 1
            elif coin == 10:
                cD += 1
            else:
                cQ += 1
            i -= coin
        if cP > mxP:
            mxP = cP
        if cN > mxN:
            mxN = cN
        if cD > mxD:
            mxD = cD
        if cQ > mxQ:
            mxQ = cQ
    return {'pennies':mxP, 'nickels':mxN, 'dimes':mxD, 'quarters':mxQ}

def min_change_table(V, C):
    m, n, minIdx = C+1, len(V), 0
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum = float('inf')
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return solution

Executing min_any_change() yields the answer we were looking for: {'pennies': 4, 'nickels': 1, 'dimes': 2, 'quarters': 3}. As a test, we can try removing a coin of any denomination and checking if it is still possible to make change for any amount in the range 1..99:

from itertools import combinations

def test(lst):
    sums = all_sums(lst)
    return all(i in sums for i in xrange(1, 100))

def all_sums(lst):
    combs = []
    for i in xrange(len(lst)+1):
        combs += combinations(lst, i)
    return set(sum(s) for s in combs)

If we test the result obtained above, we get a True:

test([1, 1, 1, 1, 5, 10, 10, 25, 25, 25])

But if we remove a single coin, no matter what denomination, we'll get a False:

test([1, 1, 1, 5, 10, 10, 25, 25, 25])

For this problem, Greedy approach gives a better solution than DP or others. Greedy approach: Find the largest denomination that is lesser than the required value and add it to the set of coins to be delivered. Lower the required cents by the denomination just added and repeat until the required cents becomes zero.

My solution (greedy approach) in java solution:

public class MinimumCoinDenomination {

    private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};

    public static Map<Integer, Integer> giveCoins(int requiredCents) {
        if(requiredCents <= 0) {
            return null;
        }
        Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();

        int dollar = requiredCents/100;
        if(dollar>0) {
            denominations.put(100, dollar);
        }
        requiredCents = requiredCents - (dollar * 100);

        //int sum = 0;
        while(requiredCents > 0) {
            for(int i = 1; i<coinsDenominations.length; i++) {
                if(requiredCents < coinsDenominations[i]) {
                    //sum = sum +coinsDenominations[i-1];
                    if(denominations.containsKey(coinsDenominations[i-1])) {
                        int c = denominations.get(coinsDenominations[i-1]);
                        denominations.put(coinsDenominations[i-1], c+1);
                    } else {
                        denominations.put(coinsDenominations[i-1], 1);
                    }
                    requiredCents = requiredCents - coinsDenominations[i-1];
                    break;
                }
            }
        }
        return denominations;
    }

    public static void main(String[] args) {
        System.out.println(giveCoins(199));
    }

}

Inspired from this https://www.youtube.com/watch?v=GafjS0FfAC0 following
1) optimal sub problem 2) Overlapping sub problem principles introduced in the video

using System;
using System.Collections.Generic;
using System.Linq;

namespace UnitTests.moneyChange
{
    public class MoneyChangeCalc
    {
        private static int[] _coinTypes;

        private Dictionary<int, int> _solutions;

        public MoneyChangeCalc(int[] coinTypes)
        {
            _coinTypes = coinTypes;
            Reset();
        }

        public int Minimun(int amount)
        {
            for (int i = 2; i <= amount; i++)
            {
                IList<int> candidates = FulfillCandidates(i);

                try
                {
                    _solutions.Add(i, candidates.Any() ? (candidates.Min() + 1) : 0);
                }
                catch (ArgumentException)
                {
                    Console.WriteLine("key [{0}] = {1} already added", i, _solutions[i]);
                }
            }

            int minimun2;
            _solutions.TryGetValue(amount, out minimun2);

            return minimun2;
        }

        internal IList<int> FulfillCandidates(int amount)
        {
            IList<int> candidates = new List<int>(3);
            foreach (int coinType in _coinTypes)
            {
                int sub = amount - coinType;
                if (sub < 0) continue;

                int candidate;
                if (_solutions.TryGetValue(sub, out candidate))
                    candidates.Add(candidate);
            }
            return candidates;
        }

        private void Reset()
        {
            _solutions = new Dictionary<int, int>
                {
                    {0,0}, {_coinTypes[0] ,1}
                };
        }
    }
}

Test cases:

using NUnit.Framework;
using System.Collections;

namespace UnitTests.moneyChange
{
    [TestFixture]
    public class MoneyChangeTest
    {
        [TestCaseSource("TestCasesData")]
        public int Test_minimun2(int amount, int[] coinTypes)
        {
            var moneyChangeCalc = new MoneyChangeCalc(coinTypes);
            return moneyChangeCalc.Minimun(amount);
        }

        private static IEnumerable TestCasesData
        {
            get
            {
                yield return new TestCaseData(6, new[] { 1, 3, 4 }).Returns(2);
                yield return new TestCaseData(3, new[] { 2, 4, 6 }).Returns(0);
                yield return new TestCaseData(10, new[] { 1, 3, 4 }).Returns(3);
                yield return new TestCaseData(100, new[] { 1, 5, 10, 20 }).Returns(5);
            }
        }
    }
}

In general, if you have your coins COIN[] and your "change range" 1..MAX, the following should find the maximum number of coins.

Initialise array CHANGEVAL[MAX] to -1

For each element coin in COIN:
  set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
  For each index I over CHANGEVAL:
    if CHANGEVAL[I] != -1:
      let coincount = CHANGEVAL[I]
      For each element coin in COIN:
        let sum = coin + I
        if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
          COINS[sum]=coincount+1

I don't know if the check for coin-minimality in the inner conditional is, strictly speaking, necessary. I would think that the minimal chain of coin-additions would end up being correct, but better safe than sorry.

This might be a generic solution in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CoinProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            var coins = new int[] { 1, 5, 10, 25 }; // sorted lowest to highest
            int upperBound = 99;
            int numCoinsRequired = upperBound / coins.Last();
            for (int i = coins.Length - 1; i > 0; --i)
            {
                numCoinsRequired += coins[i] / coins[i - 1] - (coins[i] % coins[i - 1] == 0 ? 1 : 0);
            }
            Console.WriteLine(numCoinsRequired);
            Console.ReadLine();
        }
    }
}

I haven't fully thought it through...it's too late at night. I thought the answer should be 9 in this case, but Gabe said it should be 10... which is what this yields. I guess it depends how you interpret the question... are we looking for the least number of coins that can produce any value <= X, or the least number of coins that can produce any value <= X using the least number of coins? For example... I'm pretty sure we can make any value with only 9 coins, without nickels, but then to produce 9... you need...oh... I see. You'd need 9 pennies, which you don't have, because that's not what we chose... in that case, I think this answer is right. Just a recursive implementation of Thomas' idea, but I don't know why he stopped there.. you don't need to brute force anything.

Edit: This be wrong.

There are a couple of similar answers up there but my solution with Java seems a little easier to understand. Check this out.

public static int findMinimumNumberOfCoins(int inputCents) {

     // Error Check, If the input is 0 or lower, return 0.
     if(inputCents <= 0) return 0;

     // Create the List of Coins that We need to loop through. Start from highest to lowewst.
     // 25-10-5-1
     int[] mCoinsArray = getCoinsArray();

     // Number of Total Coins.
     int totalNumberOfCoins = 0;

     for(int i=0; i < mCoinsArray.length; i++) {

         // Get the Coin from Array.
         int coin = mCoinsArray[i];

         // If there is no inputCoin Left, simply break the for-loop
         if(inputCents == 0) break;

         // Check If we have a smaller input than our coin
         // If it's, we need to go the Next one in our Coins Array.
         // e.g, if we have 8, but the current index of array is 10, we need to go to 5.
         if(inputCents < coin) continue;

         int quotient = inputCents/coin;
         int remainder = inputCents%coin;

         // Add qutient to number of total coins.
         totalNumberOfCoins += quotient;

         // Update the input with Remainder.
         inputCents = remainder;
     }

     return totalNumberOfCoins;
 }

 // Create a Coins Array, from 25 to 1. Highest is first.
 public static int[] getCoinsArray() {

     int[] mCoinsArray = new int[4];
     mCoinsArray[0] = 25;
     mCoinsArray[1] = 10;
     mCoinsArray[2] = 5;
     mCoinsArray[3] = 1;

     return mCoinsArray;
 }

I wrote this algorithm for similar kind of problem with DP, may it help

public class MinimumCoinProblem {

    private static void calculateMinumCoins(int[] array_Coins, int sum) {

        int[] array_best = new int[sum];

        for (int i = 0; i < sum; i++) {
            for (int j = 0; j < array_Coins.length; j++) {
                    if (array_Coins[j] <= i  && (array_best[i] == 0 || (array_best[i - array_Coins[j]] + 1) <= array_best[i])) {
                        array_best[i] = array_best[i - array_Coins[j]] + 1;
                    }
            }
        }
        System.err.println("The Value is" + array_best[14]);

    }


    public static void main(String[] args) {
        int[] sequence1 = {11, 9,1, 3, 5,2 ,20};
        int sum = 30;
        calculateMinumCoins(sequence1, sum);
    }

}

Here's a simple c# solution using Linq.

internal class Program
{
    public static IEnumerable<Coin> Coins = new List<Coin>
    {
        new Coin {Name = "Dime", Value = 10},
        new Coin {Name = "Penny", Value = 1},
        new Coin {Name = "Nickel", Value = 5},
        new Coin {Name = "Quarter", Value = 25}
    };
    private static void Main(string[] args)
    {
        PrintChange(34);
        Console.ReadKey();
    }
    public static void PrintChange(int amount)
    {
        decimal remaining = amount;
        //Order coins by value in descending order
        var coinsDescending = Coins.OrderByDescending(v => v.Value);
        foreach (var coin in coinsDescending)
        {
            //Continue to smaller coin when current is larger than remainder
            if (remaining < coin.Value) continue;
            // Get # of coins that fit in remaining amount
            var quotient = (int)(remaining / coin.Value);

            Console.WriteLine(new string('-',28));
            Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
            //Subtract fitting coins from remaining amount
            remaining -= quotient * coin.Value;
            if (remaining <= 0) break; //Exit when no remainder left
        }
        Console.WriteLine(new string('-', 28));
    }
    public class Coin
    {
        public string Name { get; set; }
        public int Value { get; set; }
    }
}    

A vb version

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, _
                              ByVal e As System.EventArgs) Handles Button1.Click
        For saleAMT As Decimal = 0.01D To 0.99D Step 0.01D
            Dim foo As New CashDrawer(0, 0, 0)
            Dim chg As List(Of Money) = foo.MakeChange(saleAMT, 1D)
            Dim t As Decimal = 1 - saleAMT
            Debug.WriteLine(t.ToString("C2"))
            For Each c As Money In chg
                Debug.WriteLine(String.Format("{0} of {1}", c.Count.ToString("N0"), c.moneyValue.ToString("C2")))
            Next
        Next
    End Sub

    Class CashDrawer

        Private _drawer As List(Of Money)

        Public Sub New(Optional ByVal QTYtwoD As Integer = -1, _
                       Optional ByVal QTYoneD As Integer = -1, _
                       Optional ByVal QTYfifty As Integer = -1, _
                       Optional ByVal QTYquarters As Integer = -1, _
                       Optional ByVal QTYdimes As Integer = -1, _
                       Optional ByVal QTYnickels As Integer = -1, _
                       Optional ByVal QTYpennies As Integer = -1)
            _drawer = New List(Of Money)
            _drawer.Add(New Money(2D, QTYtwoD))
            _drawer.Add(New Money(1D, QTYoneD))
            _drawer.Add(New Money(0.5D, QTYfifty))
            _drawer.Add(New Money(0.25D, QTYquarters))
            _drawer.Add(New Money(0.1D, QTYdimes))
            _drawer.Add(New Money(0.05D, QTYnickels))
            _drawer.Add(New Money(0.01D, QTYpennies))
        End Sub

        Public Function MakeChange(ByVal SaleAmt As Decimal, _
                                   ByVal amountTendered As Decimal) As List(Of Money)
            Dim change As Decimal = amountTendered - SaleAmt
            Dim rv As New List(Of Money)
            For Each c As Money In Me._drawer
                change -= (c.NumberOf(change) * c.moneyValue)
                If c.Count > 0 Then
                    rv.Add(c)
                End If
            Next
            If change <> 0D Then Throw New ArithmeticException
            Return rv
        End Function
    End Class

    Class Money
        '-1 equals unlimited qty
        Private _qty As Decimal 'quantity in drawer
        Private _value As Decimal 'value money
        Private _count As Decimal = 0D

        Public Sub New(ByVal theValue As Decimal, _
                       ByVal theQTY As Decimal)
            Me._value = theValue
            Me._qty = theQTY
        End Sub

        ReadOnly Property moneyValue As Decimal
            Get
                Return Me._value
            End Get
        End Property

        Public Function NumberOf(ByVal theAmount As Decimal) As Decimal
            If (Me._qty > 0 OrElse Me._qty = -1) AndAlso Me._value <= theAmount Then
                Dim ct As Decimal = Math.Floor(theAmount / Me._value)
                If Me._qty <> -1D Then 'qty?
                    'limited qty
                    If ct > Me._qty Then 'enough 
                        'no
                        Me._count = Me._qty
                        Me._qty = 0D
                    Else
                        'yes
                        Me._count = ct
                        Me._qty -= ct
                    End If
                Else
                    'unlimited qty
                    Me._count = ct
                End If
            End If
            Return Me._count
        End Function

        ReadOnly Property Count As Decimal
            Get
                Return Me._count
            End Get
        End Property
    End Class
End Class

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)

As I understood if you are using standard currency system values then its super easy to count the minimum number of coins just by a single loop. Just always consume the max coin value and if it not possible check for the next option. But if you have a system like you have coins such as 1,2,3,4 then its not working. I guess the whole idea of having coins as 1,2,5,10,25 is to make computation easy for humans.

The task

Find the least number of coins required, that can make any change from 1 to 99 cent.

differs from the task

For each single change from 1 to 99 cent, find the least number of coins required.

because the solution might be a complete different multiset of coins.

Suppose you have not (1), (5), (10), and (25) cent coins, but (1), (3), (5), and (17) cent coins: To make the change for 5, you only need one (5) coin; but for all changes from 1 to 5 you need two (1) coins and one (3) coin, not any (5) coin.

The greedy algorithm iterates from the smallest value to the largest, concerning the change values and coin values:

With 1x(1) you get all change values below 2.

To make a change of 2, you need an additional coin,
which could have any value up to 2;
choose greedy -> choose the largest -> (1).

With 2x(1) you get all change values below 3.

To make a change of 3, you need an additional coin,
which could have any value up to 3;
choose greedy -> choose the largest -> (3).

With 2x(1)+1x(3) you get all change values below 6.

To make a change of 6, you need an additional coin,
which could have any value up to 6;
choose greedy -> choose the largest -> (5).

and so on...

That is in Haskell:

coinsforchange [1,3,5,17] 99
where
    coinsforchange coins change = 
        let f (coinssofar::[Int],sumsofar::Int) (largestcoin::Int,wanttogoto::Int) = 
                let coincount=(max 0 (wanttogoto-sumsofar+largestcoin-1))`div`largestcoin
                 in (replicate coincount largestcoin++coinssofar,sumsofar+coincount*largestcoin)
         in foldl f ([],0) $ zip coins $ tail [c-1|c<-coins] ++ [change]

And in C++:

void f(std::map<unsigned,int> &coinssofar,int &sumsofar, unsigned largestcoin, int wanttogoto)
{
    int x = wanttogoto - sumsofar + largestcoin - 1;
    coinssofar[largestcoin] = (x>0) ? (x / largestcoin) : 0;
    //returns coinssofar and sumsofar;
}
std::map<unsigned,int> coinsforchange(const std::list<unsigned> &coins, int change)
{
    std::map<unsigned,int> coinssofar;
    int sumsofar=0;
    std::list<unsigned>::const_iterator coin = coins.begin();
    unsigned largestcoin = *coin;
    for( ++coin ; coin!=coins.end() ; largestcoin=*(coin++))
        f(coinssofar,sumsofar,largestcoin,(*coin) - 1);
    f(coinssofar,sumsofar,largestcoin,change);
    return coinssofar;
}

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.

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.

Edit: As the commenters have noted, I have misinterpreted the question. (The question is very similar to a basic CS problem I see students at the college having to solve...) waves hand This is not the answer you are looking for. That said, while the original answer is wrong, we can use it as a stepping stone to an O(n) solution.

So, take the wrong answer below, which only solves for a single value (ie, the minimum coinage required for 68 cents) and simply run it for every value.

changes = []
for amount in xrange(1, 100): # [1, 99]
    changes.append( run_the_algo_below( amount ) )
# Take the maximum for each coin type.
# ie, if run_the_algo_below returns (q, d, n, p):
change = [0, 0, 0, 0]
for c in changes:
    change = [max(c[i], change[i] for i in xrange(0, 4)]

Now, this will certainly give you a valid answer, but is it a minimal answer? (this is the harder part. Currently my gut says yes, but I'm still thinking about this one...)

(The wrong answer)

Wow. Loops? Dynamic programming? Really folks?

In Python:

amount = ( your_amount_in_cents )

quarters = amount // 25
dimes = amount % 25 // 10
nickels = amount % 25 % 10 // 5
pennies = amount % 25 % 10 % 5

Probably some of those modulo operations can be simplified...

This isn't hard, you just need to think about how you make change in real life. You give out quarters until adding another quarter would put you over the desired amount, you give out dimes until adding another dime would put you over the desired amount, so on. Then, convert to mathematical operations: modulo and division. Same solution applies for dollars, converting seconds into HH:MM:SS, etc.