Optimum Change

05/11/2016

Below are 2 functions that will return the optimal amount of change for a given amount out of £1, 50p, 20p, 10p, 5p, 2p and 1p coins. The first function returns the optimal amount, whereas the second function returns the optimal amount from a finite amount of coins, here defined in the array 'quantities'.

If there are not enough coins to make up the desired amount the function will not return any coins and it will not remove any remaining coins, instead it will just print the message 'insufficient coinage'.

JavaScript Code

var coins = [100, 50, 20, 10, 5, 2, 1];
var quantities = [11, 24, 0, 99, 5, 2, 11];

var unlimitedCoins = function(amount) {
	var change = [];
	var total = 0;

	coins.forEach(function(coin) {
		while (total + coin <= amount) {
			change.push(coin);
			total += coin;
		}
	});
	return change;
};

var limitedCoins = function(amount) {
	var change = [];
	var total = 0;
	var origionalQuantity = _.clone(quantities);
	coins.forEach(function(coin, coinIndex) {
		while (total + coin <= amount && quantities[coinIndex] > 0) {
			quantities[coinIndex]--;
			change.push(coin)
			total += coin;
		}
	});
	var sum = 0;
	change.forEach(function(coin){
		sum += coin;
	});
	if (sum != amount) {
		quantities = origionalQuantity;
		console.log("insufficient coinage");
		return [];
	}
	return change;
}

To view a live demo of this code in action click here