Create a gist now

Instantly share code, notes, and snippets.

#!/usr/bin/env node
// Solve the "Coin Change" problem using a bottom-up dynamic programming
// approach. The time complexity is O(n * coins.length) since we have a nested
// loop. The storage complexity is the same, as we store a matrix.
//
// * `coins` is an array of the coin values, eg. [ 1, 2, 3 ]. We assume it
// to be non-empty.
// * `n` is the amount, eg. 4 cents.
//
// The top-down solution is also possible (memoization), but can causes
// stack-overflows for large inputs.
//
function findPermutations(coins, n) {
// The 2-dimension buffer will contain answers to this question:
// "how much permutations is there for an amount of `i` cents, and `j`
// remaining coins?" eg. `buffer[10][2]` will tell us how many permutations
// there are when giving back 10 cents using only the first two coin types
// [ 1, 2 ].
var buffer = new Array(n + 1);
for (var i = 0; i <= n; ++i)
buffer[i] = new Array(coins.length + 1);
// For all the cases where we need to give back 0 cents, there's exactly
// 1 permutation: the empty set. Note that buffer[0][0] won't ever be
// needed.
for (var j = 1; j <= coins.length; ++j)
buffer[0][j] = 1;
// We process each case: 1 cent, 2 cent, etc. up to `n` cents, included.
for (i = 1; i <= n; ++i) {
// No more coins? No permutation is possible to attain `i` cents.
buffer[i][0] = 0;
// Now we consider the cases when we have J coin types available.
for (j = 1; j <= coins.length; ++j) {
// First, we take into account all the known permutations possible
// _without_ using the J-th coin (actually computed at the previous
// loop step).
var value = buffer[i][j - 1];
// Then, we add all the permutations possible by consuming the J-th
// coin itself, if we can.
if (coins[j - 1] <= i)
value += buffer[i - coins[j - 1]][j];
// We now know the answer for this specific case.
buffer[i][j] = value;
}
}
// Return the bottom-right answer, the one we were looking for in the
// first place.
return buffer[n][coins.length];
}
// The boring stuff: parsing and printing.
//
function processData(input) {
var lines = input.split('\n');
var coins = lines[0].split(',').map(function (s) {return +s;});
var n = +lines[1];
var res = findPermutations(coins, n);
console.log(res);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
@mpenkov
mpenkov commented Feb 13, 2014

Thanks for documenting your solution. The comments are very helpful. Do you mean "combination" instead of "permutation"?

@PratyushRaizada94

Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment