Teaching Kids Programming: Videos on Data Structures and Algorithms
Find the minimum number of coins required to make n cents. You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.
Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 3
Output
3
Explanation
You can make this with 3 pennies.Example 2
Input
n = 5
Output
1
Explanation
You can make this with a 5 cent coin.Example 3
Input
n = 6
Output
2
Explanation
You can make this with a 5 cent coin and a 1 cent coin.Hints:
Pay most with the largest denomination and so on.
Compute Minimum Number of Changes by Greedy Algorithm
Because we can always make up the changes using 1 cent, we can greedy choose the largest coin. The greedy strategy works as we can always find solutions for each amount.
1 2 3 4 5 6 7 8 9 10 | class Solution: def minChange(self, n): ans = 0 for i in (25, 10, 5, 1): this = n // i ans += this n -= this * i if n == 0: break return ans |
class Solution: def minChange(self, n): ans = 0 for i in (25, 10, 5, 1): this = n // i ans += this n -= this * i if n == 0: break return ans
The above can be implemented using One-liner – trying the coin 25 and then get its remainder and try coin 10 and so on.
1 2 3 | class Solution: def minChange(self, n): return n // 25 + (n % 25) // 10 + (n % 25 % 10) // 5 + (n % 25 % 10 % 5) |
class Solution: def minChange(self, n): return n // 25 + (n % 25) // 10 + (n % 25 % 10) // 5 + (n % 25 % 10 % 5)
The Greedy Algorithms of making change in this problem is O(1) time and O(1) space – as the number of coins is fixed (1, 5, 10 and 25).
Dynamic Programming Algorithms to Make Change
Usin Dynamic Programming Algorithm – we know the DP transition function:
for i in [1, 5, 10 and 25].
Given .
The Bottom Up DP to solve this:
1 2 3 4 5 6 7 8 9 | class Solution: def minChange(self, n): dp = [float("inf")] * (n + 1) dp[0] = 0 for i in range(1, n + 1): for j in (1, 5, 10, 25): if i >= j and dp[i - j] != math.inf: dp[i] = min(dp[i], dp[i - j] + 1) return dp[n] |
class Solution: def minChange(self, n): dp = [float("inf")] * (n + 1) dp[0] = 0 for i in range(1, n + 1): for j in (1, 5, 10, 25): if i >= j and dp[i - j] != math.inf: dp[i] = min(dp[i], dp[i - j] + 1) return dp[n]
And the Top Down (implemented via Recursion with Memoization aka @cache) is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | import sys class Solution: def minChange(self, n): sys.setrecursionlimit(max(100000, n)) @cache def f(n): if n == 0: return 0 if n < 0: return math.inf ans = math.inf for c in (1, 5, 10, 25): ans = min(ans, f(n - c) + 1) return ans return f(n) |
import sys class Solution: def minChange(self, n): sys.setrecursionlimit(max(100000, n)) @cache def f(n): if n == 0: return 0 if n < 0: return math.inf ans = math.inf for c in (1, 5, 10, 25): ans = min(ans, f(n - c) + 1) return ans return f(n)
In Top Down DP, we have to enlarge the recursion limit via sys.setrecursionlimit (to verify using sys.getrecursionlimit).
Both DP algorithms have O(N) time and O(N) space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Sum of Four Numbers using Depth First Search Algorithm
Next Post: How to Mask Email Addresses using PHP Function?