Last active
June 22, 2022 02:51
-
-
Save jeanlauliac/8674996 to your computer and use it in GitHub Desktop.
Solve the "Coin Change" coding challenge https://www.hackerrank.com/contests/programming-interview-questions/challenges/coin-change
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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); | |
}); |
Thanks!
There is much shorter solution that uses recursion
function count(coins, sum, numCoins) {
if (numCoins === undefined) {numCoins = coins.length;}
if (sum == 0) {return 1;}
if (sum < 0) {return 0;}
if (numCoins <= 0 && sum > 0) {return 0;}
return count(coins, sum, numCoins - 1) + count(coins, sum - coins[numCoins - 1], numCoins);
}
console.log(count([1,2,3], 4));
Same solution in C#
public static long findPermutations(int n, List<long> c)
{
// 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 ].
long[][] buffer = new long[n + 1][];
for (var i = 0; i <= n; ++i)
buffer[i] = new long[c.Count + 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 <= c.Count; ++j)
buffer[0][j] = 1;
// We process each case: 1 cent, 2 cent, etc. up to `n` cents, included.
for (int 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 (int j = 1; j <= c.Count; ++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 (c[j - 1] <= i)
value += buffer[i - c[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][c.Count];
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for documenting your solution. The comments are very helpful. Do you mean "combination" instead of "permutation"?