CODEWITHSUNDEEP
javascriptalgorithmdynamic-programming
TechnoCorner
TechnoCorner

Reputation: 5135

javascript making change algorithm

I'm solving this problem "Making change" in javascript:

Question:

Given an amount of money, an array of coin denominations, compute the number of ways to make the amount of money with coins of the available denominations.

Example:

For amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations:

1¢, 1¢, 1¢, 1¢

1¢, 1¢, 2¢

1¢, 3¢

2¢, 2¢

I found a solution:

var makeChange = function(total){
  var count = 0;
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];

  var changer = function(index, value){

    var currentCoin = coins[index];

    if( index === 0){
      if( value % currentCoin === 0){
        count++;
      }
      return;
    }

    while( value >= 0 ){
      changer(index-1, value);
      value -= currentCoin;
    }
  }
  changer(coins.length-1, total);
  return count;
};

makeChange(200);

Problem(s):

  1. Can someone explain to me what is going on? I tried following the code but i get lost in between the recursion.

I understand that he is taking the final coin value and he is substracting from the given total. (But why?) I'm kinda lost.

  1. When value >= 0 in the while loop, It keeps looping around increasing the index, i couldn't understand why.

Can someone make sense out of this algorithm?

Sorry, just started learning Dynamic Programming.

Thank you,

Upvotes: 1

Views: 3892

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Let's track what happens with makeChange(4):

The function changer gets defined then called for the first time.

value = 4, index = 7, coins[7] = 200

Since the variable, index is not 0, we move on to the while loop.

A second call to changer is made with index 6

Meanwhile, the first call continues the 'while'
loop but since 200 has been subtracted from 'value',
'value' is now less than 0 so the 'while' loop terminates
and this first call does nothing more.

(Keep in mind that the variable 'value' is distinct 
and private to each call, so the 'while' loop only 
affects the 'value' in its own function call.)

Ok, now this pattern continues with all the function calls that have index pointing to a coin larger than value until index is 1.

value = 4, index = 1, coins[1] = 2

This time more happens in the while loop:

We get the function call, 'changer(0,4)', 
AND a second function call, 'changer(0,2)', 
after we subtract 2 from 'value', which was 4,
AND a third function call, 'changer(0,0)', 
after we subtract 2 from 'value', which was 2.

These 3 calls respectively represent:

   1 + 1 + 1 + 1
   2 + 1 + 1
   2 + 2

Each time the line 'value -= currentCoin' is executed,
it represents the start of another set of choices for 
solutions that include that coin.

4 % coins[0] = 0, meaning 4 is divisible by 1 represents 1 + 1 + 1 + 1

4 - 2 folllowed by 2 % 1 represents 2 + 1 + 1

and 4 - 2 - 2 represents 2 + 2

Total count: 3

Upvotes: 1

Related Questions