Commit4b76b49

authored

Added CoinChange Algorithm (TheAlgorithms#260)

* Added CoinChange Algorithm* Minor Changes* Minor Changes* Minor Changes

1 parent3277751 commit4b76b49Copy full SHA for 4b76b49

File tree

+45

-0

lines changed

+45

-0

lines changed

Lines changed: 45 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,45 @@`
	`1`	`+functionchange(coins,amount){`
	`2`	`+constcombinations=newArray(amount+1).fill(0)`
	`3`	`+combinations[0]=1`
	`4`	`+`
	`5`	`+for(leti=0;i<coins.length;i++){`
	`6`	`+constcoin=coins[i]`
	`7`	`+`
	`8`	`+for(letj=coin;j<amount+1;j++){`
	`9`	`+combinations[j]+=combinations[j-coin]`
	`10`	`+}`
	`11`	`+}`
	`12`	`+returncombinations[amount]`
	`13`	`+}`
	`14`	`+`
	`15`	`+functionminimumCoins(coins,amount){`
	`16`	`+// minimumCoins[i] will store the minimum coins needed for amount i`
	`17`	`+constminimumCoins=newArray(amount+1).fill(0)`
	`18`	`+`
	`19`	`+minimumCoins[0]=0`
	`20`	`+`
	`21`	`+for(leti=1;i<amount+1;i++){`
	`22`	`+minimumCoins[i]=Number.MAX_SAFE_INTEGER`
	`23`	`+}`
	`24`	`+for(leti=1;i<amount+1;i++){`
	`25`	`+for(letj=0;j<coins.length;j++){`
	`26`	`+constcoin=coins[j]`
	`27`	`+if(coin<=i){`
	`28`	`+constsubRes=minimumCoins[i-coin]`
	`29`	`+if(subRes!==Number.MAX_SAFE_INTEGER&&subRes+1<minimumCoins[i]){`
	`30`	`+minimumCoins[i]=subRes+1`
	`31`	`+}`
	`32`	`+}`
	`33`	`+}`
	`34`	`+}`
	`35`	`+returnminimumCoins[amount]`
	`36`	`+}`
	`37`	`+`
	`38`	`+functionmain(){`
	`39`	`+constamount=12`
	`40`	`+constcoins=[2,4,5]`
	`41`	`+console.log('Number of combinations of getting change for '+amount+' is: '+change(coins,amount))`
	`42`	`+console.log('Minimum number of coins required for amount :'+amount+' is: '+minimumCoins(coins,amount))`
	`43`	`+}`
	`44`	`+`
	`45`	`+main()`

Comments

(0)