Last active
December 28, 2021 15:42
-
-
Save trykhov/369f02b91f5695ed636fff06f64aef21 to your computer and use it in GitHub Desktop.
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
| // assume that coins is an array of positive integers | |
| // assume that amount is non-negative | |
| function minCoinChange(coins, amount) { | |
| // create an array to hold the minimum number of coins to make each amount | |
| // amount + 1 so that you will have indices from 0 to amount in the array | |
| const minCoins = new Array(amount + 1).fill(Infinity); | |
| // there are 0 ways to make amount 0 with positive coin values | |
| minCoins[0] = 0; | |
| // look at one coin at a time | |
| for(let coin of coins) { | |
| for(let i = 0; i <= amount; i += 1) { | |
| // make sure the difference between the current amount and the current coin is at least 0 | |
| // replace the minimum value | |
| if((i - coin) >= 0) minCoins[i] = Math.min(minCoins[i], minCoins[i - coin] + 1); | |
| } | |
| } | |
| // if the value remains Infinity, it means that no coin combination can make that amount | |
| return minCoins[amount] !== Infinity ? minCoins[amount] : -1; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment