Code Challenge: Change Dispenser

I recently encountered a brain teaser that asked to take an amount of change and return the equivalent in dollars and coins.

Here's the five-minute solution I first came up with.

function makeChange (money) {
    var i, num,
        output = [],
        coins  = [
            [100, "dollar",  "dollars" ],
            [25,  "quarter", "quarters"],
            [10,  "dime",    "dimes"   ],
            [5,   "nickel",  "nickels" ],
            [1,   "penny",   "pennies" ]
        ];
    money = money * 100; // avoid float precision issues
    for (i = 0; i < coins.length; i++) {
        num = Math.floor(money / coins[i][0]);
        money -= num * coins[i][0];
        if (num) {
            output.push(num + " " + coins[i][num > 1 ? 2 : 1]);
        }
    }
    return output.join(", ");
}

makeChange(0.37); // "1 quarter, 1 dime, 2 pennies"

I feel like I'm missing something, though. How would you improve this code to make it shorter, faster, or otherwise better?

32 thoughts on “Code Challenge: Change Dispenser”

  1. That’s the typical way I’ve seen these problems solved, like the ‘6 days 3 hours and 10 minutes ago’ style for dates.

    I’ve been thinking a bit about it and I can’t think of any other way which doesn’t involve unrolling the loop.

  3. Pingback: Darkness Productions’ Blog » Code Challenge: Change Dispenser

  4. I also didn’t find a better way to do this. My improvement would be to replace Math.floor with
    num = money / coins[i][0]|0;
    which seems to be a little faster. For positive numbers, both operations are equal.

  5. I’m not sure but I’m seeing an option of having the coins array being passed to the function and the function calling itself recursively.
    That way you can pass different coin collections.
    I’m not sure if that would be faster though…

    (Oh… and I also would go with the modulus operator)

  6. I don’t know how I did it, but I convinced myself that a recursive approach was a good idea. It was fun at least.

    var coins = [
	[100, 'dollar', 'dollars'],
	[25, 'quarter', 'quarters'],
	[10, 'dime', 'dimes'],
	[5, 'nickel', 'nickels'],
	[1, 'penny', 'pennies']
];

function checkCoin(change, coin, accum) {
	if (coin >= coins.length) { return accum; }
	var num = Math.floor(change / coins[coin][0]);
	if (num) { accum.push(num + " " + coins[coin][num > 0 ? 2 : 1]); }
	return checkCoin(change % coins[coin][0], coin + 1, accum);
}

function makeChange(money) {
	return checkCoin(money * 100, 0, []).join(", ");
}

  7. @Travis Parker, it had to be done. 🙂

    Nice tweaks, people. I guess I wasn’t too far off mark. You could also save a few characters by changing the order of the coins child arrays to e.g. ['penny','pennies',1], because then you could change the plurality selector from coins[i][num > 1 ? 2 : 1] to coins[i][num > 1].

  8. «
    – Le compte est bon
    – Pas mieux
    »

    (from “Des chiffres et des lettres”, original french game known as “coutdown” in UK)

  9. careful with that different plurality selector – quick check with firebug console shows [‘f’, ‘t’][5 > 3] is undefined. Unfortunately it needs some extra coercion: [‘f’, ‘t’][Number(5 > 3)]

  10. Oh yeah, duh, it will try to access the “true” or “false” properties of the array unless you convert the boolean to a number. Thanks for correcting that.

  14. I just give it a try. It isn’t very dynamic anymore but its shorter/faster 🙂

    function makeChange(m) {
var i
x=[]
c=[[100,"dollar"],[25,"quarter"],[10,"dime"],[5,"nickel"],[1,"penn"]]
m*=100
for(i=0;i<5;i++){
p=c[i]
n=m/p[0]>>0
m-=n*p[0]
if(n)x.push(n+" "+p[1]+(n>1?(i<4?"s":"ies"):(i<4?"":"y")))
}
return x.join(", ")
}
alert(makeChange(0.37)); // "1 quarter, 1 dime, 2 pennies"

  15. Here is an example of a general solution to what i call the atm machine problem. Formatted for readability, not speed. It basically separates the solution from any particular problem. Its not shorter or faster, but i believe its ‘better’ in the sense that it allows you to solve the problem in a real world situation. What happens if you dont have enought quarters? What would be the next solution?

    function makeChange(n, kArray)
{
   var s;
   
   function possible(n, i, solution)
   {
      if(n == 0)
         return result.push(solution);

      if(n > 0 && i < kArray.length)
      {
         s = solution.concat();
         s[i] = s[i] ? s[i] + 1 : 1;
         possible(n - kArray[i], i, s);
         
         if(++i < kArray.length)
            possible(n, i, solution);
      }
   }

   var result = new Array();
   possible(n, 0, []);

   return result;
}

    To solve your particular problem:

    var result = makeChange(37, [100, 25, 10, 5, 1]);
alert(result[0]); // alerts [,1,1,,2]

    This tells us that to solve our problem we should give the user 1×25,1×10, and 2×1.

    The result has a length of 24 (so theres 24 possible solutions) which you can enumerate incase you dont have some of the required change – i.e. if you ‘machine’ is out of quarters just loop the results until you have a solution that doesn’t use them.
    Results are in order of least amount of change to greatest amount.

    For speed i would try to replace recursion with looping.

  16. Pingback: atm machine problem 
  17. function changer(amt)
{
    var coins = {100:'Dollar',25:'Quarter',10:'Dime',5:'Nickel',1:'Cent'};
    var money = [];
    amt = amt * 100;
    for(var coin in coins)
    {
        var num = (amt / coin >> 0);
        if(num>0) money.push(num + " " + coins[coin] + (num>1?"s":""));
        amt -= num * coin;
    }
    return money.join(", ");
}
changer(2.68);

  19. hi, im jannah from philippines. please help me guys. all i need is a java code for change… please help me.. thanks a lot..

  20. This is coming in a bit late, but this is a well-known CS problem. The easiest solution involves using a greedy algorithm, but it may not yield the optimum solution (the least # of coins). The best solution involves dynamic programming which will always yield the optimum solution.

  22. “for(i=0;i>0
    m-=n*p[0]
    if(n)x.push(n+” “+p[1]+(n>1?(i<4?”s”:”ies”):(i<4?””:”y”)))
    }”

    Good lord, if I had a programmer give me code like that I’d beat them senseless.

  23. Ha, Ben, I completely agree — code should be formatted for human-readability and maintenance, not brevity/number of characters… Gave me a headache just looking at that solution.

  24. Here’s a quick 2 line recursive I threw together… in the name of silly frugality – I just put the names that won’t take an ‘s’ in the [2] part of the array. : )

    var n = [
    [10000, “Hundred”],
    [ 5000, “Fifty”, “Fifties”],
    [ 2000, “Twenty”, “Twenties”],
    [ 1000, “Ten”],
    [ 500, “Five”],
    [ 200, “Two”],
    [ 100, “Dollar”],
    [ 25, “quarter”],
    [ 10, “dime”],
    [ 5, “nickel”],
    [ 1, “penny”, “pennies”],
    [ 0]
    ];

    var output = [];
    var i = 0, x = 0;

    function makeChange(money) {
    if (x = Math.floor(money / n[i][0]))
    output.push(x + ” ” + (x <= 1 ? n[i][1] : !n[i][2] ? n[i][1] + “s” : n[i][2]));
    return isNaN(n[i + 1]) ? makeChange(money % n[i++][0]) : output;
    }

    makeChange(123279.96 * 100).join(“\n”);

  25. Didn’t think about that but just saw the ATM problem – that can be solved by running a checkInventory(array) on the array which nulls out or flags any change not available (in the above recursive) so the algorithm is easily adaptable.

    -John

  26. Looking at the length of the other solutions around on here and the web (didn’t see them before and never realized this is a famous problem) I think that code I just posted is

    (c) 2009, John Vivenzio, All Rights Reserved

    LOL

    Great blog by the way!

  27. Last One… with inventory of bills and coins and shows remainder if can’t make exact change.

    var b = [
    // checkInventory to null out what’s not available (on hand is b[i][1])
    [10000, 0, “Hundred”],
    [ 5000, 1, “Fifty”, “Fifties”],
    [ 2000, 0, “Twenty”, “Twenties”],
    [ 1000, 0, “Ten”],
    [ 500, 0, “Five”],
    [ 200, 0, “Two”],
    [ 100, 0, “Dollar”],
    [ 25, 0, “quarter”],
    [ 10, 0, “dime”],
    [ 5, 0, “nickel”],
    [ 1, 0, “penny”, “pennies”],
    [ 0]
    ];

    function makeChange(money) {
    if (b[i][1] && (x = Math.floor(money / b[i][0])))
    output.push(x + ” ” + (x <= 1 ? b[i][2] : !b[i][3] ? b[i][2] + “s” : b[i][3]));
    return isNaN(b[i + 1]) ? makeChange(b[i][1] ? money % b[i++][0] : (i++, money)) :
    output.push(“Remainder: $” + money / 100), output;
    }

    makeChange(123279.96 * 100).join(“\n”);

  28. Obscure bug?

    When testing just now I found if you enter makeChange(279.96 * 100) – it rounds to 27995.9999 when multiplied by 100 – very bizarre. …using Firefox 3.5b4 – reminds me of the Pentium 59.999… days.

  29. Does shorter and no “var” statements == better? Probably not, but it was fun to slap together and I enjoy taking advantage of array methods whenever possible.

    function makeChange(money) {
    return [
    [100, ‘dollar’],
    [25, ‘quarter’],
    [10, ‘dime’],
    [5, ‘nickel’],
    [1, ‘penny’, ‘pennies’]
    ].reduce(function(state, coin, cnt) {
    if(cnt = (state.amount / coin[0]) ^ 0) {
    state.change.push(cnt + ‘ ‘ + (cnt > 1 ? coin[2] || coin[1] + ‘s’ : coin[1]));
    state.amount %= coin[0];
    }
    return state;
    }, { amount: money * 100, change: [] }).change.join(‘, ‘);
    }

  30. I’m impressed!!! Really informative blog post here my friend. I just wanted to comment u0026 say keep up the quality work.

  32. The backend part of your company supports these profit centers.

    In addition, many of the words used started to take on
    slightly different meanings, depending on the context in which they are used.
    The Unit is powered by the Main chip adopting the CORTEX A8 core Sam – Sung
    S5PV210,and CPU frequency up to 1GHz, Memory
    512MB, internal 2G memory space for TV and Internet integration.

Leave a Reply

Your email address will not be published. Required fields are marked *