How to implement an algorithm for calculating change for a vending machine ?

0

Given a vending machine which has denominations of change/currency as [1c, 2c, 3c, 4c and 5c], how
to implement an efficient function getChange() that will return the optimal amount of change denominations,
when buying goods worth x cents ?

Answered question
0

Below is a sample implementation in Javascript with different test cases

// getChange(5, 0.99) // should return [1,0,0,0,0,4]

// 1c, 5c, 10c, 25c, 50c, and $1.
init();

function init() {

var cash_tendered = 500;

for (var i = 0; i <= cash_tendered; i++)


getChange(cash_tendered, i);
}

function getChange(M, P) {

var change = M– P;

var denominations = [1, 5, 10, 25, 50, 100];

var change_integer = change– change % 100;

var change_fraction = change– change_integer;

var output = [0, 0, 0, 0, 0, 0];

for (var i = denominations.length– 1; i >= 0; i–) {


var integer = parseInt(change_integer / denominations[i]);


if (integer >= 1) {



output[i] = integer;



change_integer -= denominations[i] * integer;


}


var fraction = parseInt(change_fraction / denominations[i]);


if (fraction >= 1) {



output[i] = fraction;



change_fraction -= denominations[i] * fraction;


}

}

document.write("For getting change of " + (M - P) + " cents (or " + (M - P) / 100 + "$) vending machine will return denominations as : [", output, "] which corresponds to [1c, 5c, 10c, 25c, 50c, 100c] respectively<br/><br/>");
}

Changed status to publish
Write your answer.

Categories