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

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 ?

goli202084 Answered question

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/>"); }

goli202084 Changed status to publish