# Using Python tricks to find Minimum Coin Change (Amazon Interview)

What is the coin change problem? The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem and has applications wider than just currency. Read more: Wiki

My code:

def coin_change(n,coins,known_results):
min_coins = n

if n in coins:
known_results[n] = 1
return 1

elif known_results[n] > 0:
return known_results[n]

else:
for i in [c for c in coins if c<=n]:
count = 1 + coin_change(n-i,coins,known_results)
if count < min_coins:
min_coins = count

known_results[n] = min_coins

return min_coins

coins = [1,2,3]
n = 4
known_results = [0]*(n+1)
print(coin_change(n,coins,known_results))


Question: This code works fine and perfectly but can it be done better and more efficiently using python tricks giving it an edge more the other languages? Can it be more efficient and better?

• n is the amount you have to generate coin change for. Oct 3, 2020 at 20:26

Welcome to Code Review! Your code looks fine, and is fairly easy to follow. A few points to note though:

Since your initial if-elif clauses are returning values immediately, no need to wrap an else (and even elif) there:

if n in coins:
known_results[n] = 1
return 1
if known_results[n] > 0:
return known_results[n]
for i in [c for c in coins if c<=n]:
.
.


is achieving the same thing.

In python, multiple assignments can be done in a single statement:

known_results[n] = min_coins = count


As an aside, you can make use of type hinting to make the values and parameters more understandable. If I was only reading through the function definition, I'd have no idea what known_results was supposed to be.

When I copy&paste your code into my editor, it immediately greets me with 81(!!!) errors and warnings. To be fair, some of these are duplicates, because I have multiple linters configured. However, about 20 of those are real.

# PEP8 violations

The standard community coding style for the Python community is defined in Python Enhancement Proposal 8 – Style Guide for Python Code. You should always follow the guidelines of PEP8. There are plenty of tools available that can flag and even auto-correct violations of PEP8.

Here's just a couple that my editor flagged (and auto-corrected automatically, so I didn't have to do a single thing):

• Space after comma: Pretty much everywhere where you use a comma, you squish everything together without whitespace. You should have a space after the comma.
• Space around operators: You should have whitespace on both sides of a binary infix operator. Sometimes you do that, sometimes you don't, e.g. here [c for c in coins if c<=n]
• Indentation should be 4 spaces. You use 5 spaces for the first level of indentation, then 3 spaces for the second level except in the elif where you use 7.
• You have 2 blank lines before the else:. In general, spacing with a function should only be 1 blank line.
• You have 1 blank line after the function. There should be 2 blank lines after a function or class.
• Docstring: Your function should have a docstring explaining its usage. (Note: all the above violations were automatically fixed by my editor, this is the only one that couldn't be auto-corrected.)

# Consistency

It is very important to be consistent. When people read your code, and you do the same thing two different ways, they will automatically assume that you want to tell them something, that the difference is somehow meaningful.

I mentioned a couple of inconsistencies above, e.g. the fact that you sometimes use whitespace around operators and sometimes don't.

Even if you don't believe in style guides, you should at least be consistent with yourself.

# Linter

You should use a linter, preferably one with an auto-correct functionality. When I hit "Save" in my editor, of the 81 errors and warnings I mentioned earlier, 78 get fixed automatically, leaving only 3 (of which one is a duplicate, because as I mentioned, I have multiple linters configured).

As mentioned above, the only PEP8 violation that couldn't be auto-corrected is the missing documentation.

The other remaining issue is something already mentioned in hjpotter92's answer: since you return directly from the if, there is no need for the elif. Once I remove the el, I get a new issue telling me the same thing for the else.

# Redundant statement

In the first if, you assign to known_results[n] but then immediately return 1. Since the return ends the execution of the function, and known_results is local to the function, there is no way that this variable can be used any further, therefore the assignment is unnecessary and can just be removed.

# Redundant assignment

Also, as mentioned in hjpotter92's answer, the two assignments in the if branch inside the for loop can be chained.

# Truthiness / falsiness

In elif condition, you check whether known_results[amount] is greater than 0. Since you initialize it with zero, and only ever add to it, what you are semantically doing is basically checking whether you have ever put a value in. In Python, 0 is a false value, so instead of checking for known_results[amount] > 0, you could simply check for known_results[amount].

# Naming

n and c are not very descriptive names. Try to find names that better reveal the intent of those variables. For example n might be renamed to amount and c to coin.

In fact, you wrote in your comment under the question:

n is the amount you have to generate coin change for.

If you have to write a comment like this, either in code or in this case under the code, that is a good sign that the name is not good enough. If you have to say something like n is the amount, that is a good indication that n should be called amount, because then you wouldn't have to explain that it is the amount!

i would be acceptable for an index in a loop, but it isn't an index here. It is an element of a collection, not an index into a collection or a loop index. Actually, it could again be called coin, although that might be confusing.

Thinking about it, maybe coins should be called denominations and c should then be denomination.

Also, I would expect a function called coin_change to compute the actual coins for the change, not simply the number of coins.

# Datatypes

Since it doesn't make sense to specify the same denomination multiple times, and the order of the denominations doesn't matter, the denominations could be a Set (or even a FrozenSet since it is never mutated) rather than a List.

Or, does the order matter? It is actually not clear, and could benefit from some documentation if it does indeed matter.

Likewise, known_results probably makes more sense to be a defaultdict.

# Type Annotations

Python 3 supports (function) type annotations since the very first release in 2008 and variable annotations for a while. In more recent times, the typing module with predefined types has been added. Also, there is the Mypy static type checker for Python.

It is a good idea to take advanced of these tools, even if just for documentation.

# API

known_results is a private internal implementation detail of your (recursive) implementation. It is an accumulator whose only purpose is to keep state in your recursive calls. It shouldn't be part of the public API, you shouldn't force the caller to know what to pass here as an argument.

At the very least, you should make it an optional parameter with a default argument, so that the caller doesn't have to pass it:

def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
def minimum_number_of_coins_for_change_rec(
amount: int, known_results: DefaultDict[int, int]
) -> int:
pass # …


However, the main reason why we pass the accumulator as an argument in a recursive function when we do functional programming is that in functional we are not allowed to mutate state, and thus the arguments on the function call stack are one of the very few places where we can keep state. However, you are mutating known_results anyway, so we don't have to pass it along as an argument, it is enough to define it outside of the recursive function:

def def coin_change(amount, denominations, known_results=[0] * (amount + 1)):


But actually, you shouldn't even give the caller a chance to accidentally pass the wrong argument. It is better to remove it from the parameter list completely.

The standard way of introducing an additional parameter just for purposes of state-keeping during recursion is to introduce a new nested function for the recursion, and call that from the outer function with the correct argument. Something like this:

def minimum_number_of_coins_for_change(amount: int, denominations: Set[int]) -> int:
known_results: DefaultDict[int, int] = defaultdict(int)

def minimum_number_of_coins_for_change_rec(amount: int) -> int:
min_coins = amount

if amount in denominations:
return 1

if known_results[amount]:
return known_results[amount]

for coin in [
denomination for denomination in denominations if denomination <= amount
]:
count = 1 + minimum_number_of_coins_for_change_rec(
amount - coin
)
if count < min_coins:
known_results[amount] = min_coins = count

return min_coins

return minimum_number_of_coins_for_change_rec(amount)

denominations: Set[int] = {1, 2, 3}
amount = 5

print(minimum_number_of_coins_for_change(amount, denominations))


Unfortunately, there are now still two PEP8 violations in the code: too long lines. I will leave them in here, since there are multiple different ways to tackle this, one of which is better names, which I will leave to you.

# API, pt. 2

It seems to me that the amount you want to compute change for changes much more often than the denominations. So, it could make sense to have a coin_changer object with specific denominations that can then compute change for those denominations multiple times. Something like this:

from collections import defaultdict
from typing import DefaultDict, Set

class CoinChanger:
def __init__(self, denominations: Set[int]):
self.denominations = denominations

def minimum_number_of_coins_for_change(self, amount: int) -> int:
known_results: DefaultDict[int, int] = defaultdict(int)

def minimum_number_of_coins_for_change_rec(amount: int) -> int:
min_coins = amount

if amount in self.denominations:
return 1

if known_results[amount]:
return known_results[amount]

for coin in [
denomination
for denomination in self.denominations
if denomination <= amount
]:
count = 1 + minimum_number_of_coins_for_change_rec(amount - coin)
if count < min_coins:
known_results[amount] = min_coins = count

return min_coins

return minimum_number_of_coins_for_change_rec(amount)

denominations: Set[int] = {1, 2, 3}
amount = 5

coin_changer = CoinChanger(denominations)

print(coin_changer.minimum_number_of_coins_for_change(amount))


At the very latest now that we have turned our code into a module containing a class, we should make sure that the test code at the bottom does not accidentally get executed just because someone imported the module. In general, such code should always be wrapped into a __main__ guard:

if __name__ == '__main__':
denominations: Set[int] = {1, 2, 3}
amount = 5

coin_changer = CoinChanger(denominations)

print(coin_changer.minimum_number_of_coins_for_change(amount))


Although ideally, it shouldn't be there at all, it should be a proper unit test in a separate test module. (And there should be more tests, including corner cases such as empty denominations, an amount of 0, negative amounts, combinations of amounts and denominations where giving change is impossible, etc.)

• Type hints were added in Python 3 and Python 3 was released in 2008. So, alternatively, we could say, type hints (at least for functions) have been part of Python 3 since the beginning. BTW, thanks for reminding me that Python calls them annotations, I believe the "hint" terminology crept into my mind from PHP. Oct 4, 2020 at 22:38
• Thank you, TIL the date on the PEP and the date it's actually released can be significantly different. :) Sorry I think I've made a mess here! Python has both function annotations (PEP 3107) and type hints (PEP 484). I.e def foo(bar: "baz") is using function annotations but not type hints, where def foo(bar: str) would be using both. I'll leave you be now, just don't want to potentially be the cause for making you say something technically wrong and meet someone's ire. Oct 4, 2020 at 22:47