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?*

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.

Well, the only minor improvement I can see is changing:

money -= num * coins[i][0];

for:

money %= coins[i][0];

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.

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)

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.

@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]`

.ยซ

– Le compte est bon

– Pas mieux

ยป

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

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

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.

The Ruby Quiz asked this question some months ago: http://rubyquiz.com/quiz154.html

I ended up with a min-max with alpha-beta pruning-like algorithm (except that you only have to care about the alpha and forget the beta).

This is way faster than using math.Floor:

num = ( money / coins[i][0] ) >> 0;

Well my proposal is here.. ๐

http://serious-javascript.blogspot.com/2008/06/code-challenge.html

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

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?

To solve your particular problem:

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.

@g You used cents ๐ thats way easier, but just smart, I guess.

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

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.

Should be noted that for American coins greedy yields the optimum solution, but in general it doesn’t.

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

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.

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

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