# Number Division Theory

I have a JavaScript function that takes in a user number (total amount placed on a betting table in denominations of 50) and returns an Array of the optimum chips (lowest # required) to form each stack.

My function works, the correct array for each value tested is output - but since this should be running on the client browser with a fast response time for smooth UI I feel like the code is not optimised.

Is there a better, more efficient (+ mathematically solid) way of computing the same output?

Any suggestions would be appreciated.

//number will be validated before running through function to make sure it has a factor of 50.

function chipStack(number) {
var k = 0; //1k chip
var f = 0; //500 chip
var t = 0; //300 chip
var o = 0; //100 chip
var fi = 0; // 50 chip

k = Math.floor(number / 1000);
var number2 = number % 1000

if (number2 === 0) {
return [k, f, t, o, fi];
} else {
f = Math.floor(number2 / 500)
var number3 = number2 % 500
}

if (number3 === 0) {
return [k, f, t, o, fi];
} else {
t = Math.floor(number3 / 300)
var number4 = number3 % 300
}

if (number4 === 0) {
return [k, f, t, o, fi];
} else {
o = Math.floor(number4 / 100)
var number5 = number4 % 100
}

if (number5 === 0) {
return [k, f, t, o, fi];
} else {
fi = Math.floor(number5 / 50)
var number6 = number5 % 50
}

if (number6 === 0) {
return [k, f, t, o, fi];
} else {
return "Something isn't right " + number6;
}
}

• I guess you could write the code to look more compact, but inlined as it is here should execute fast. – TonyWilk Mar 20 '14 at 17:31
• There won't be performance problems, but there are several poor programming practices in that code (else after return, var inside conditional code, etc). – Pointy Mar 20 '14 at 17:33

You could compress the code as follows. It doesn't check for early exit conditions, but since it's running on the front-end anyway, i.e. not at high volumes, the performance won't be noticeably degraded.

function chipStack(n){
var chipValues = [1000,500,300,100,50];
var stack = [];
chipValues.forEach(function(e,i){
stack.push(Math.floor(n / e));
n -= (stack[stack.length-1] * e);
})
return stack;
}


Since you asked for mathematical background…

In general, the Change-making problem is a knapsack problem, which is NP-hard. However, for sane sets of currency denominations, a simple greedy algorithm works.

For your set of denominations, { 1000, 500, 300, 100, 50 }, the greedy algorithm applies. (There is, however, an amount with two optimal solutions: 600 = 500 + 100 = 300 + 300.) Therefore, your greedy algorithm and @MartVandeVen's simplified implementation of it will work.