You find yourself in Bananaland trying to buy a banana. You are super rich so you have an unlimited supply of banana-coins, but you are trying to use as few coins as possible.
The coin values available in Bananaland are stored in a sorted array
coins = 1, and for each
i (0 < i < coins.length)
coins[i] is divisible by
coins[i - 1]. Find the minimal number of banana-coins you’ll have to spend to buy a banana given the banana’s
coins = [1, 2, 10] and
price = 28, the output should be
minimalNumberOfCoins(coins, price) = 6.
You have to use
10 twice, and
2 four times.
- [time limit] 4000ms (py)
- [input] array.integer coinsThe coin values available in Bananaland.Constraints:
1 ≤ coins.length ≤ 5,
1 ≤ coins[i] ≤ 120.
- [input] integer priceA positive integer representing the price of the banana.Constraints:
8 ≤ price ≤ 250.
- [output] integerThe minimal number of coins you can use to buy the banana.
def minimalNumberOfCoins(coins, price): r = 0 l=len(coins)-1 while price>0: while price<coins[l]: l-=1 if l<0: break; if l<0: break price -= coins[l] r+=1 return r