Number Division Theory

Question

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;
 }
}

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

Answer 1

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;
}

Answer 2

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.