This community-built FAQ covers the "Change Please " code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Python challenge _Change Please _

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply () below!
You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? Like () to up-vote the contribution!

from itertools import combinations_with_replacement, chain
def change_options(input_money, coins):
res = []
for i in range(1, int(input_money/min(coins))+1):
res.append([x for x in combinations_with_replacement(coins, i) if sum(x) == input_money])
return len(list(chain.from_iterable(res)))
print(change_options(5, [1, 2, 5, 10, 100]))

This was a particularly difficult challenge for me.
I didn’t use the itertools module.

Instead, I tried to generate the combinations [with replacement] myself.
I did it using a branching recursion (meaning recursion in a loop) but only going - from the that number in the coins list - forward (by using indices). I put a starting_index parameter in the recursive function to accomplish this.
It took some time to figure that part out, actually coding it took less time.
(I put the recursive function an an internal function inside of change_options.)

my code

def change_options(input_money, coins, sort = False):
length = len(coins)
if sort:
coins = sorted(coins)
# recursive function:
def get_count(money_remaining, starting_index = 0):
# base cases for recursion:
if money_remaining < 0:
return 0
elif money_remaining == 0:
return 1
count = 0
# recursion done in loop to get branching recursions
for i in range(starting_index, length):
coin = coins[i]
if money_remaining == coin:
count += 1
if (sort):
break
elif money_remaining > coin:
# main recursion
count += get_count(money_remaining - coin, i)
return count
# end of get_count function
return get_count(input_money)
# end of change_options function
print(change_options(5, [1, 2, 5, 10, 100]))

I also came up with a way to display all the options using a similar technique.
I used tuples to store the arrangement being considered so far (and based on its sum, accept or reject it, or use it to generate a longer combination).
I made helper functions for printing the tuple or appending to it (to make a new tuple).

longer version

def append_to(arrangement, additional):
# generator function:
def iterator_with_additional(iterable, appended):
for x in iterable:
yield x
yield appended
iterator = iterator_with_additional(arrangement, additional)
return tuple( y for y in iterator )
def print_tuple(tup):
length = len(tup)
if length == 0:
print("()")
elif length == 1:
print("({})".format(tup[0]))
else:
print(tup)
def change_options(input_money, coins, sort = False):
length = len(coins)
if sort:
coins = sorted(coins)
options = []
# internal function for recursion
def get_options(so_far, starting_index = 0):
# so_far is coins used so far, as a tuple
total_so_far = sum(so_far)
# base cases
if total_so_far > input_money:
return 0
elif total_so_far == input_money:
options.append(so_far)
return 1
count = 0
# recursion done in loop for a branching recursion
for i in range(starting_index, length):
coin = coins[i]
if (total_so_far + coin) == input_money:
options.append(append_to(so_far, coin))
count += 1
if (sort):
break
elif (total_so_far + coin) < input_money:
# main recursion
incomplete = append_to(so_far, coin)
count += get_options(incomplete, i)
return count
# end of get_options function
get_options(tuple()) # inserts the tuples into the options list
for option in options:
print_tuple(option)
return len(options)
# end of change_options function
print(change_options(5, [1, 2, 5, 10, 100]))

My code is long and unsophisticated compared to some of the other solutions to the challenges I’ve seen on the forums.
I actually did similar recursion in loops for a related challenge using Java.

I was able to pass the tests using dynamic programming. I can’t figure out how to post my code on here so I’ll just outline my approach.

Given ‘input_money’ (let’s say this equals m) and coins, a list of integers indexed by j for 0 <= j <= n

Let num(i, j) = the number of ways to make change for i using the coins 0 through j. We would like to return the value of num(m, n)

We have the recursion: num(i, j) = num(i - coins[j], j) + num(i, j-1) … we need to be careful here to check that coins[j] <= i first of course

This represents that when making change for i we can choose to either use our largest denomination coin available (the jth coin) or we can choose to not use it and attempt to make change with the remaining j-1 coins available.

With this recursion we also need to initialize value of num(0, j) = 1 for all 0 <= j <= n because there is only one way to make change for 0.

Using this recursion and initialization we can set up a memoization table in the usual way. In this case, the table would be m x n and so this is an O(mn) runtime complexity and O(mn) space complexity.

def change_options(i, c):
if i == 0:
return 1 #nothing is one permutation
if len(c) == 0 or i < 0:
return 0 #no coins to choose or overshooting
return change_options(i-c[0], c) + change_options(i,c[1:])
print(change_options(5, [1, 2, 5, 10, 100]))

base cases is

finding change for no money (1 permutation)

no change available for some money or using coins causes overshooting of money (no permutation available)

recursive case
given amount of money i and list of coin c
the permutation is the sum of the following subcases

case where u make use of the first coin (the amount of money to change will be lesser)

case where u never use the first coin (the money amount still stay the same but the you have lesser choices for coins)

[codebyte language=python]
from itertools import combinations_with_replacement, chain
def change_options(input_money, coins):
res = []
for i in range(1, int(input_money/min(coins))+1):
res.append([x for x in combinations_with_replacement(coins, i) if sum(x) == input_money])
return len(list(chain.from_iterable(res)))
print(change_options(5, [1, 2, 5, 10, 100]))
[/codebyte]

def change_options(input_money, coins, sequences=None, prev_coins=None):
if sequences is None:
sequences = []
if prev_coins is None:
prev_coins = []
if input_money == 0:
prev_coins = sorted(prev_coins)
if "".join([str(val) for val in prev_coins]) not in ["".join([str(val) for val in lst]) for lst in sequences]:
sequences.append(prev_coins)
return sequences
coins = [coin for coin in coins if input_money - coin >= 0]
for coin in coins:
change_options(input_money - coin, coins, sequences, prev_coins+[coin])
return len(sequences)
print(change_options(5, [1, 2, 5, 10, 100]))

I wanted to be able to see the sequences as well. Without that, it can be shortened. I found this problem particularly challenging as well and was curious to see other solutions (some of which are expectedly much better than mine).