Coin Change problem with Greedy Approach in Python

Question

I am trying to implement greedy approach in coin change problem, but need to reduce the time complexity because the compiler won't accept my code, and since I am unable to verify I don't even know if my code is actually correct or not. The function should return the total number of notes needed to make the change. If change cannot be obtained for the given amount, then return -1. Return 1 if the amount is equal to one of the currencies available in the denomination list.

def make_change(denomination_list, amount):

    denomination_list.sort()
    n = len(denomination_list)
    i = n - 1
    ans = 0
    x = 0
    while i>= 0 :
        while denomination_list[i]<= amount:
            ans = +1
            amount -= denomination_list[i]
            i -= 1
        if amount == 0:
            x = 1
        elif amount<0:
            x = -1
    return x

    amount= 20
    denomination_list = [1,15,10]
    print(make_change(denomination_list, amount))

Your code has many minor problems, and two major design flaws. The first design flaw is that the code removes exactly one coin at a time from the amount. That will cause a timeout if the amount is a large number. For example, if the amount is 1000000, and the largest coin is 15, then the loop has to execute 66666 times to reduce the amount to 10. That can fixed with division. The quotient is the number of coins, and the remainder is what's left over after removing those coins. For example, 1000000 // 15 is 66666 and 1000000 % 15 is 10. — user3386109
The second design flaw is that the greedy algorithm isn't optimal for some instances of the coin change problem. The code has an example of that. When amount is 20 and the coins are [15,10,1], the greedy algorithm will select six coins: 15,1,1,1,1,1 when the optimal answer is two coins: 10,10. Another example is an amount 7 with coins [3,2]. The greedy algorithm will select 3,3 and then fail, whereas the correct answer is 3,2,2. — user3386109
@user3386109 than you for your feedback, I'll keep this is mind. However, it is specifically mentioned in the problem to use greedy approach as I am a novice. — shrekh

Amitai Irron Amitai Irron · Accepted Answer · 2020-06-02T18:35:49

You want to minimize the use of list indexes if possible, and iterate over the list itself. Here is a code that works:

# Pre-process denomination list before function, sorting in decreasing order
denomination_list = [1,15,10]
denomination_list.sort(reverse = True)
# Ensure ones are available for change (or infinite loop may result)
if denomination_list[-1] != 1:
    denomination_list.append(1)

def make_change(denomination_list, amount):
    change = []
    # Iterate through coins
    for coin in denomination_list:
        # Add current coin as long as not exceeding ampoiunt
        while amount:
            if coin <= amount:
                change.append(coin)
                amount -= coin
            else:
                break
    return change

amount= 43
print(make_change(denomination_list, amount))

This will work for non-integer values of amount and will list the change for a rounded down amount.

Coin Change problem with Greedy Approach in Python

1 Answers