{{ message }}

Instantly share code, notes, and snippets.

# jeanlauliac/coins.js

Last active Jul 6, 2019
 #!/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` 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 won't ever be // needed. for (var j = 1; j <= coins.length; ++j) buffer[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; // 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.split(',').map(function (s) {return +s;}); var n = +lines; 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); });

### svolvohome commented Apr 5, 2017
 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)); ``````