...

/

Solution: Counting Money

Solution: Counting Money

This review provides a detailed analysis of the different ways to solve the counting money challenge.

Solution: greedy approach

Caution!! This is not the most optimized solution. It is only to give you an idea of how the greedy algorithm works.

def find_min_coins(v, coins_available):
"""
This function finds the minimum number of coins
:param v: Total amount
:param coins_available: Coins available in the machine
:return: A list of total coins
"""
# Initialize result
result = []
n = len(coins_available)
# Traverse through all available coins
for i in reversed(range(n)):
while v >= coins_available[i]:
v -= coins_available[i]
result.append(coins_available[i])
return result
# Main program to test the above code
if __name__ == "__main__":
coins_available = [1, 5, 10, 25] # The available coins are in increasing order
print(find_min_coins(19, coins_available))

Explanation

The simple greedy idea is to start from the largest possible coin available and keep adding coins, ...