Change Calculator

A dig at one of those code puzzlers from dzone. Thanks to Abhi (a buddy) for sharing it with me and instilling the urge for this adventure. I have utilized a subset generation algorithm (highlighted in code) from my mentor and friend (Pai) here.

Change Calculator 

Say you are given an infinite number of coins in the following denominations:

  • 25 cents
  • 10 cents
  • 5 cents
  • 1 cent

Write a method that would take an integer parameter named change. Work out all the permutations that can return that amount given the coins that you have available. For example, calculateChange(5) would return

  1. 1 x 5c
  2. 5 x 1c
var calculateChange = function (denominations, amount) {
	'use strict';
	var changeSets = 0,
		printChangeSet = function (denominationSet) {
			var matchFactors = [],
				findCombinationSet = function (denominationIndex, cumilativeSum) {
					var transientSum = 0,
						i = 1,
						denomination = denominationSet[denominationIndex],
						factorCount = denominationSet.length;
					while (transientSum <= amount) {
						//Pretty Printing
						matchFactors[denominationIndex] = i.toString() + " x " + denomination.toString() + "c";
						transientSum = cumilativeSum + (denomination * i);
						if ((denominationIndex + 1) === factorCount) {
							if (transientSum === amount) {
								changeSets += 1;
								console.log(changeSets + ". " + matchFactors);
							}
						} else {
							findCombinationSet(denominationIndex + 1, transientSum);
						}
						i += 1;
					}
				};
			findCombinationSet(0, 0);
		},
		// This function computes the possible denomination sets
		generateChangeSets = function () {
			var bitcount = denominations.length,
				mask = Math.pow(2, bitcount),
				i = 1,
				j = 0,
				k = 1,
				denominationSet = null,
				denominationSum = 0;
			while (i < mask) {
				j = 0;
				denominationSet = [];
				denominationSum = 0;
				while (j < bitcount) {
					if ((i & (k << j)) > 0) {
						denominationSet.push(denominations[j]);
						denominationSum += denominations[j];
					}
					j += 1;
				}
				if (denominationSum <= amount) {
					printChangeSet(denominationSet);
				}
				i += 1;
			}
		};
	generateChangeSets();
};
/*jslint indent: 4, maxerr: 1, passfail: false, browser: false, devel: true, windows: false, rhino: false, undef: true, node: true, bitwise: true */

To test this, simply execute:

calculateChange([1, 5, 10, 25], 5);

The decomposition technique utilized here (that of finding all the denomination sets first and then searching for the combinations that would yield the amount) doesn’t hold good against this classic NP-Hard problem where despite parallelization, you cannot cheat death owing to stack overflow for the larger sets, lower denominations and higher amounts.

Advertisements