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.

  2. 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.

  3. 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)

  4. 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(", ");
    }
  5. @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].

  6. ยซ
    – Le compte est bon
    – Pas mieux
    ยป

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

  7. 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)]

  8. 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.

  9. 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"
  10. 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.

  11. 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);
  12. hi, im jannah from philippines. please help me guys. all i need is a java code for change… please help me.. thanks a lot..

  13. 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.

  14. “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.

  15. 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.

  16. 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”);

  17. 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

Leave a Reply

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