Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note: You may assume that you have an infinite number of each kind of coin.
Pseudo Code
// define array and fill
// * array is amt + 1
// sort coins arr
// set 0 index to 0
// loop thru amount
// loop through coins in amount
// if coin is less than outer index
// assign min of arr index and 1 plus arr index minus inner index, to arr index
// else break
// if arr amt less Inf then arr amt else -1
Solution
function coinChange(coins: number[], amt: number){
// define array and fill
let arr = new Array(amt+1).fill(Infinity)
// sort coins arr
let coinsSorted = coins.sort((a,b)=>a-b)
// set 0 index to 0
arr[0] = 0
// loop thru amount
let i=0
while(i<=amt){
// loop through coins in amount
let coin: number
for (coin of coins){
// if coin is less than outer index
if(coin<=i){
// assign min of arr index and 1 plus arr index minus inner index, to arr index
arr[i] = Math.min(arr[i], 1+arr[i-coin])
}
// else break
else{
break
}
}
i++
}
// if arr amt less Inf then arr amt else -1
return amt<Infinity ? arr[amt] : -1
}
const coins = [1, 2, 5], amount = 11
comments powered by Disqus