﻿ JavaScript - What's wrong with this coin change algorithm

# JavaScript - What's wrong with this coin change algorithm

I'm trying to use the greedy algorithm for calculating the minimum number of coins needed to reach an amount in JavaScript

The return result will be an array consisting of the number of coins at each level

I decided to make a function that would solve this, but it doesn't work

``````window.addEventListener('load', function(e) {
function calculateChange(coins, total) {
var sum = 0;
var dispatched = [];
for (var i = 0; i < coins.length;i++) {
dispatched[c] = 0;
}

while (sum < total) {
for (var c = 0; c < coins.length; c++) {
while (total - sum >= coins[c]) {
total += coins[c];
dispatched[c]++;
}
}
}
return dispatched;
}

}, false);
``````

The calculateChange function takes in two parameters, an array of coin values and the amount.

First step would be to initialize a sum variable which shows the amount of change already dispatched. I will also create an array variable that will hold the number of times a certain coin has been dispensed.

To do this, I will iterate over the coins array and set all the values to 0. This is important if I don't know the number of different coin values

Next I thought of having a while condition that checks whether the amount has been reached

If it hasn't, I will start a for loop that iterates over all coin values. As for the greedy algorithm, as the index increases, the coin value decreases. This is to use as few coins as possible

To prevent jumping down the coin hierarchy there will be a while loop nested inside this for loop. This while loop will check whether the largest coin can still be used.

If not the loop condition is satisfied and the while loop will end. The for loop will continue by incrementing the index. We will move down to the next lower level coin. The process will repeat

The output I was expecting was this

``````[2,1,1,0,2]
``````

This means 2 50s, 1 quarter, 1 dime, and 2 pennies

In this function, this is supposed to represent the values of dispatched, which is the return value. Running the above code, I do not get a return value

The only explanation I can have is I'm using the loops wrong. I don't see it even upon examination

What am I missing here. Insights are greatly appreciated

Apparently, the variable `sum` is initialized with `0` and never updated, so the loop

``````while (sum < total)
``````

will run forever, as `total` is increased, but never decreased. Perhaps you want to update `sum` instead of `total`. I guess you have mixed up the semantics of `sum` (which apparently is the value already covered with the selected coins) and `total`, which is the argument of the function.

You don't need nested loops. Instead, you can simply do an integer division at each step, by dividing and then using `Math.floor()`. That gives you the number of coins needed for the current denomination, and then you can reduce the remaining total based on that.

Also your first loop that attempts to put zeros in the `dispatched` array has the wrong variable for the array index.

So you might try something like this:

``````function calculateChange( coins, total ) {
var dispatched = [];
for( var i = 0;  i < coins.length;  i++ ) {
dispatched[i] = 0;
}

for( var c = 0;  total > 0;  c++ ) {
dispatched[c] = Math.floor( total / coins[c] );
total -= dispatched[c] * coins[c];
}
return dispatched;
}

console.log( calculateChange( [50,25,10,5,1], 137 ) );
// logs [ 2, 1, 1, 0, 2 ]
``````