Python Challenge - Change Please

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 (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 (reply) below!
You can also find further discussion and get answers to your questions over in Language Help.

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

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

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

  1. finding change for no money (1 permutation)
  2. 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

  1. case where u make use of the first coin (the amount of money to change will be lesser)
  2. case where u never use the first coin (the money amount still stay the same but the you have lesser choices for coins)
2 Likes
[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(money, coins): # Write your code here if(money < 0): return 0 elif(money == 0): return 1 else: count = 0 for i in range(len(coins)): # print(money,"-", c, "=", money -c) count += change_options(money - coins[i], coins[i:]) return count print(change_options(5, [1, 2, 5, 10, 100]))
def change_options(input_money, coins): # Write your code here coins.sort() range_max = input_money + 1 options = [0 for _ in range(range_max)] options[0] = 1 for coin_value in coins: for value in range(coin_value, range_max): if coin_value == value: options[value] += 1 elif coin_value < value: options[value] += options[value - coin_value] return options[input_money] print(change_options(5, [1, 2, 5, 10, 100])) # 4 print() print("Number of ways to break a dollar:") print(change_options(100, [1, 5, 10, 25, 50])) # 292 print() print("Number of ways to break 20 dollars (bills only):") print(change_options(20, [1, 5, 10])) # 9 print() print("Number of ways to break 20 dollars " "(bills only, including the elusive 2 dollar bill):") print(change_options(20, [1, 2, 5, 10])) # 40
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).

def change_options(input_money, coins):
  ways = [0 for amount in range(input_money + 1)]
  ways[0] = 1

  for coin in coins:
    for amount in range(1, input_money + 1):
      if coin <= amount:
        ways[amount] += ways[amount - coin]
  return ways[input_money]

print(change_options(5, [1, 2, 5, 10, 100]))
def change_options(input_money, coins): if input_money == 0: return 1 if len(coins) == 0 or input_money < 0: return 0 return change_options(input_money-coins[0], coins) + change_options(input_money,coins[1:]) print(change_options(5, [1, 2, 5, 10, 100]))
def change_options(input_money, coins):

  table = [0] * (input_money + 1)
  table[0] = 1

  for coin in coins:
    for i in range(coin, input_money + 1):
      table[i] += table[i - coin]
  
  return table[input_money]

print(change_options(5, [1, 2, 5, 10, 100]))