Change Cash Function Optimization - Javascript

Question

Today I come to your aid in favor of optimizing some code!

I was asked to solve a problem on a test a few weeks ago, and came up with this non-optimal solution since I'm beggining to learn Javascript.

I wonder if there's a way (of course there is) to make this better.

Here's the situation:

"I am a particular kind person who has an infinite ammount of $2, $5 and $10 dollar bills, and I'm willing to change cash for anyone who wants it, BUT in the most efficient way, with the minimum ammount of bills."

Since I had to return an object with the number of bills (or null in case of less than $2), I gave the following solution:

function giveChange(change){    
var two = 0;
var five = 0;
var ten = 0;
var changeToGo = change;

while(changeToGo >= 11){
    changeToGo -=10;
    ten+=1;
}

while(changeToGo >=7 && changeToGo <=11){
    changeToGo-=5;
    five+=1;
}

while(changeToGo >=2 && changeToGo <=6 ){
    if(changeToGo == 5){
        changeToGo -=5;
        five+=1;
}
    else{
        changeToGo -= 2;
        two+=1;
    }
}

if (change < 2){
    return null;
}

return {
    two: two,
    five: five,
    ten: ten
};
}

I think there must be a clever and more elegant solution (probably with mod% or something), but that monstrosity was what I was able to pull off at the time hahaha.

Any thoughts?

Answer 1

Edit: Removed he initial answer, as it was based on a misconception about the requirements.

Ok, then let's turn that around, first let's determine how many $2 bills I'll have to hand out to get to a number that's divisible by $5 bills. So for now I only care about the rests < $5 for to calculate the $2 bills.

The generic idea is, If I have a value where change%5 is 2, like $12 or $17 or $22, ... I hand out one $2 bill and I can divide the rest by 5.

For values like $14, $19, ... it's two $2 bills, for $11, $16, ... I subtract $6, and for $13, $18, ... it's $8

With that I have a static table of how many $2 bills I'd have to hand out, for every change % 5; no loops or so needed, just a simple lookup.

function giveChange(change){
  const two = change < 4? change>>1: [0,3,1,4,2][Math.floor(change) % 5],
    rest = change - two*2;

  return { 
    two,
    five: Math.floor((rest%10)/5), 
    ten: Math.floor(rest/10), 
  };
}

---

Care to explain again what this does? "change>>1" and "[0,3,1,4,2][Math.floor(change) % 5];" ?

change >> 1 is here just a shorthand for Math.floor(change/2) and deals mostly with the special cases giveChange(1) and giveChange(3); They are not interchangable, but for the range 0..4 (where I use it) they produce the same result.

let two = [0,3,1,4,2][change % 5];

//does 
let two;
if(change%5 === 0) two = 0;
if(change%5 === 1) two = 3;
if(change%5 === 2) two = 1;
if(change%5 === 3) two = 4;
if(change%5 === 4) two = 2;

And Math.floor(change) % 5 is just in case that you'll use this with floats, like giveChange(25.90)

But maybe an example explains it better

for(let change=4; change<50; ++change){
  let two = [0,3,1,4,2][change%5];
  console.log("change: %i, two: %i, rest: %i", change, two, change - two*2);
}

.as-console-wrapper{top:0;max-height:100%!important}

you see how two always always has the same 5 values in the same order, and how the rest now is divisible by 5 and or 10.

That's what this code does, it looks up the Array [0,3,1,4,2], how many $2 bills it needs use for any given change, so that the rest is divisible by 5.

Answer 2

You could take a combination algorithm and return the denominators in an array

function combine(array, sum) {

    function c(left, right, sum) {
        if (!sum) {
            result = right;
            return true;
        }
        return left.some(function (a, i, aa) {
            return a <= sum && c(aa.slice(i + (a > sum - a)), right.concat(a), sum - a);
        });
    }

    var result = [];
    c(array.sort(function (a, b) { return b - a; }), [], sum);
    return result;
}

function giveChange(change) {
    return combine([10, 5, 2], change);
}

console.log(giveChange(7));
console.log(giveChange(13));
console.log(giveChange(23));