-
Notifications
You must be signed in to change notification settings - Fork 2
/
changingCoinSums.js
97 lines (80 loc) · 3.1 KB
/
changingCoinSums.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**********************************************************************
* Problem : Coin Change *
* *
* Prompt: US Currency has coins in circulation with the *
* following value in cents: [1, 5, 10, 25, 50, 100] *
* *
* Given a value, find how many unique ways to make change *
* given the coin values in circulation. *
* *
* Input: An integer N (value from which to make change) *
* Output: An integer (number of unique ways to make change) *
* *
* Time Complexity: NA *
* Auxiliary Space Complexity: NA *
* *
* Example: input = 11 *
* output = 4 ([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], *
* [5, 1, 1, 1, 1, 1, 1], *
* [5, 5, 1], *
* [10, 1]) *
* *
* Challenge Mode: Solve coin change with you solution having: *
* Time Complexity: O(nm) *
* Auxiliary Space Complexity: O(n) *
* Hint: www.geeksforgeeks.org/dynamic-programming-set-7-coin-change *
**********************************************************************/
// //http://www.codewars.com/kata/541af676b589989aed0009e7/train/javascript
// var countChange = function(money, coins) {
// coins = Array.prototype.sort.call(coins, function(a, b){
// if (a > b){
// return -1;
// }else if (a < b){
// return 1;
// }else {
// return 0;
// }
// })
// var counter = 0;
// var addingOnCoins = function(currentTot, usableCoins){
// if (currentTot === money){
// counter++;
// return;
// }
// else if (currentTot > money){
// return;
// }
// for (var i = 0; i < usableCoins.length; i++){
// addingOnCoins(currentTot + usableCoins[i], usableCoins.slice(i));
// }
// }
// addingOnCoins(0, coins);
// return counter;
// }
var pureCoinSum = function(total, coins){
if (total === 0){
return 1;
} else if (total < 0){
return 0;
}
var ways = 0;
for (var i = 0; i < coins.length; i++){
var avail = coins.slice(i);
ways += pureCoinSum(total - coins[i], avail);
}
return ways;
}
console.log(pureCoinSum(4, [2,1])) // => 3
console.log(pureCoinSum(10, [5,2,3])) // => 4
console.log(pureCoinSum(11, [5,7])) // => 0
console.log(pureCoinSum(101, [2,4,6,8]))
console.log(pureCoinSum(500, [1,5,10,25,50,100]));
//
//
//
//
//
//
//
//
//