Hadron DaVinci

Minimum and maximum number of coins needed to make change for a $100 dollar bill? (Bounded)

05 Sep 2020 - Hadron DaVinci

Problem

You have three $20 dollar bills, five $10 dollar bills, two $5 dollar bills, and five $1 dollar bills.
How many ways can you make change for a $100 dollar bill?

Discussion

Truths:

1. This scenario is bounded since the number of each bills available is limited.
2. Even though this problem uses bills as the form of currency, it is equivalent to coins. Therefore, this is still a coin problem.
   
   

Method (Coin Change Mother Function):

In a previous post, I created a function which could be used to solve many coin change problems.
Internally, it uses a double loop along with recursion to create a list of coins that sum to the target value.
You can find more about that post here.

Example

coin_values = [20, 10, 5 1]
quantity = [3, 5, 2, 5]
target_value = 100
SOLUTIONS = []

foo(coin_values, quantity, target_solutions)
max_count = 0
min_count = 0

for s in SOLUTIONS:
    max_count = max(len(s), max_count)
    min_count = min(len(s), min_count)

print("Max Number of Bills Needed Is:", max_count)
print("Min Number of Bills Needed Is:", min_count)