How to turn money (in pence) to its individual coins?

Question

My task was to 'Write a function selectCoins that asks the user to enter an amount of money (in pence) and then outputs the number of coins of each denomination (from £2 down to 1p) that should be used to make up that amount exactly (using the least possible number of coins). For example, if the input is 292, then the function should report: 1 × £2, 0 × £1, 1 × 50p, 2 × 20p, 0 × 10p, 0 × 5p, 1 × 2p, 0 × 1p. (Hint: use integer division and remainder).'

def selectCoins():
    twopound = 200
    onepound = 100
    fiftyp = 50
    twentyp = 20
    tenp = 10
    fivep = 5
    twop = 2
    onep = 1
    a = 0
    b = 0
    c = 0
    d = 0
    e = 0
    f = 0
    g = 0
    h = 0
    money = int(input('Enter how much money you have in pence'))

    while True:
        if money >= twopound:
            money = money - twopound
            a = a + 1
        elif money >= onepound:
            money = money - onepound
            b = b + 1
        elif money >= fiftyp:
            money = money - fiftyp
            c = c + 1
        elif money >= twentyp:
            money = money - twentyp
            d = d + 1
        elif money >= tenp:
            money = money - tenp
            e = e + 1
        elif money >= fivep:
            money = money - fivep
            f = f + 1
        elif money >= twop:
            money = money - twop
            g = g + 1
        elif money >= onep:
            money = money - onep
            h = h + 1
        else:
            money = 0
        break
    print(a,b,c,d,e,f,g,h)

I am new to programming so when I run this code it just inputs '1 0 0 0 0 0 0 0' when I type 292 instead of what it should output.

Answer 1

Since you're new to coding, you should start writing the procedure you'd follow on paper, and then find out which tools you can use to automate this process.

Important

Read the full answer in order!
Don't fall for the temptation of reading the code right away.

The solutions I provide are hidden, but you can read them hovering your mouse over them or clicking on them (if you're using StackExchange mobile app, touch the "spoiler" link in each block).

The algorithm

What I'd do is:

1. Assume I have bins with coins, each bin labeled with the coin denomination.
   The bins are sorted from the largest to the lowest denomination, and I always pick as much coins as I need from the highest denomination bin before moving to the next bin.
2. Write in a piece of paper the value for which I need to calculate the number of coins of each denomination I need.
3. Start with the first bin (the one holding the highest denomination).
4. Pick as many coins I need from that bin, in such a way that I don't "overshoot" the amount written on the piece of paper (notice that this number can be zero).
   This can be done with an integer division; for example, if your value is 700 and the bin has denomination 200, you calculate the integer division 700 ÷ 200 = 3 (plus a remainder of 100)
5. Calculate the total amount of the coins I've picked.
6. Strike the value calculated in step 5 and write the remainder as a "new" value.
   Since you've already calculated the integer division in step 4, you can calculate the remainder. You can also consider that there's a "Modulo" operator in most programming languages that will give you the remainder of an integer division right away. Using the above example, 700 mod 200 = 100, which reads "700 modulo 200 is 100", or "The remainder of the integer division 700 ÷ 200 is 100".
7. Move on to the next bin of coins.
8. Repeat from step 4 until I use all the bins or the value is zero.

Example

Suppose I start with a value of 292 and I have bins with the following denominations (already sorted from highest to lowest denominations):

|  200 |  100 |   50 |   20 |   10 |    5 |    2 |    1 |
+------+------+------+------+------+------+------+------+
|   I  |   II |  III |   IV |    V |   VI |  VII | VIII |

So, let's see what happens if I apply the algorithm above:

Write the value:   292
Start with the first bin (denomination: 200)
Pick 1 coin from the bin
    The total amount picked from the bin is 200
    The remainder is 92
Strike the previous value
    The new value is 92
Move to the next bin (denomination: 100)
Pick 0 coins from the bin
    The total amount picked from the bin is 0
    The remainder is 92
Strike the previous value
    The new value is 92
Move to the next bin (denomination: 50)
Pick 1 coin from the bin
    The total amount picked from the bin is 50
    The remainder is 42
Move to the next bin (denomination: 20)
    Pick 2 coins from the bin
    The total amount picked from the bin is 20
    The remainder is 2
Move to the next bin (denomination: 10)
    Pick 0 coins from the bin
    The total amount picked from the bin is 0
    The remainder is 2
Move to the next bin (denomination: 10)
    Pick 0 coin from the bin
    The total amount picked from the bin is 0
    The remainder is 2
Move to the next bin (denomination: 5)
    Pick 0 coin from the bin
    The total amount picked from the bin is 0
    The remainder is 2
Move to the next bin (denomination: 2)
    Pick 1 coin from the bin
    The total amount picked from the bin is 2
    The remainder is 0
Done

Implementing this in Python

Python is an amazingly clear language, and makes this sort of tasks easy. So let's try to translate our algorithm to Python.

The toolbox

Assuming you're using Python 3.x, you'll need to know some operators:

• The integer division operator (//): If you divide with just a single slash, you'll get the "real division" (e.g. 3 / 2 == 1.5), but if you use a double slash, you'll get the "integer division (e.g. 3 // 2 = 1)
• The modulo operator (%): As explained above, this operator returns the remainder of a division (e.g. 7 % 4 == 3)

Used together, these operators will give you what you need on each step:

292 // 200 == 2
292 % 200 == 92

92 // 100 == 0
92 % 100 == 92

...

One useful characteristic of Python is that you can perform a "multiple assignment": You can assign multiple values to multiple variables in one single step:

# Initialize the value:
value = 292
# Initialize the denomination:
denomination = 200
# Calculate the amount of coins needed for the specified denomination
# and get the remainder (overwriting the value), in one single step:
coins, value = value // denomination, value % denomination
#              ^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^
#              |                      The remainder
#              The number of coins
#              (using integer division)

With this knowledge, we can write the solution:

Correcting your code

Remember: Read all of the above before revealing the solutions below.

def selectCoins():
    twopound = 200
    onepound = 100
    fiftyp = 50
    twentyp = 20
    tenp = 10
    fivep = 5
    twop = 2
    onep = 1
    a = 0
    b = 0
    c = 0
    d = 0
    e = 0
    f = 0
    g = 0
    h = 0
    money = int(input('Enter how much money you have in pence')) # Example: 292
    # Calculate the number of coins needed and the remainder
    # The remainder will "overwrite" the value previously held in the "money" variable
    a, money = money // twopound, money % twopound # a = 1, money = 92
    b, money = money // onepound, money % onepound # b = 0, money = 92
    c, money = money // fiftyp,   money % fiftyp   # c = 1, money = 42
    d, money = money // twentyp,  money % twentyp  # d = 2, money = 2
    e, money = money // tenp,     money % tenp     # e = 0, money = 2
    f, money = money // fivep,    money % fivep    # f = 0, money = 2
    g, money = money // twop,     money % twop     # g = 1, money = 0
    e, money = money // onep,     money % onep     # e = 0, money = 0
    print(a,b,c,d,e,f,g,h)

This solution uses both integer division and remainder to perform the calculations.

Let's do it the right way: with a loop

Let's face it: the above code is verbose. There must be a better way... and there is! Use a loop. Consider the algorithm: you repeat the steps jumping from one bin to the next and getting the number of coins you need and the remainder. This can be written in a loop. So, let's add a list to our toolbox:

denominations = [200, 100, 50, 20, 10, 5, 2, 1]

And let's store the results of each step in a second list:

coins = [] # We'll use the '.append()' method to add elements to this list

So, starting in the first "bin":

n, money = money // denominations[0] , money % denominations[0]
    coins.append(n)

Let's put this in a loop:

def select_coins_v2():
        denominations = [200, 100, 50, 20, 10, 5, 2, 1]
        coins = []
        money = int(input('Enter how much money you have in pence'))
        for i in range(len(denominations)):
            n, money = money // denominations[i], money % denominations[i]
            coins.append(n)
        print(coins)

And that's it!

Another improvement: get the denomination only once and use it twice

Notice that the code above still has an issue: you read denominations twice. It would be nice if the denomination value could be read only once. Of course, there is a way:

def select_coins_v3():
        denominations = [200, 100, 50, 20, 10, 5, 2, 1]
        coins = []
        money = int(input('Enter how much money you have in pence'))
        for d in denominations:  # 'd' will hold the value of the denomination
            n, money = money // d, money % d
            coins.append(n)
        print(coins)

As a friend of mine says: "Fast, precise and concise; not slow, difuse and confusing"

TL;DR

• In Python 3.x, the "integer division" operator is // and the remainder (modulo) operator is %.
• You can perform multiple assignement in a single line of code:
  a, b = 1, 2
• You can store the denominations in a list:
  denominations = [200, 100, 50, 20, 10, 5, 2, 1]
• You can read from the denominations list and get both the integer division and the remainder in a single step:
  n, money = money // denominations[0], money % denominations[0]
• You can write a loop that does all of the above:
  for d in denominations: n, money = money // d, money % d

---

Bonus: Use a dictionary

What if I want to print both the denominations and the number of coins of each denomination I used? You can traverse both lists with a loop, but you can also keep it simple by using a dictionary:

def select_coins_v4():
        denominations = [200, 100, 50, 20, 10, 5, 2, 1]
        coins = []
        money = int(input('Enter how much money you have in pence'))
        for d in denominations:  # 'd' will hold the value of the denomination
            n, money = money // d, money % d
            coins.append(n)
        number_of_coins = dict(zip(denominations, coins))
        print(number_of_coins)

Python offers a great deal of flexibility. Feel free to try different ways of getting what you need... and choose the easier one.

Hope this helps.

Answer 2

the cool thing about using real denominations is that the greedy solution will always find the optimal solution ... this stops holding true with weird denominations... but these problems are always easiest if you break them into parts

def get_one_change(amt_due):
    # find how many of the largest denomination that you can use is
    # ie for 60 = 1x50p is the count and number of largest
    # for 4 = 4x1p ; 21 = 2x10p ; etc
    return pence,count # ie 50,1 would be 1 50p coin

once you have this you just need to repeatedly call it and adjust your result until you have no change due

def get_change(amount_due):
   changes_due = [] # to keep track
   while amount_due:
      pence,qty_of_coin = get_one_change(amount_due)
      changes_due.append({"coin":pence,"qty":qty_of_coin})
      amount_due = amount_due - (pence*qty_of_coin)
   return changes_due

now you can just call your get_change method with your users input