## atm - return required sum using minimum amount of 100, 50 and 20 banknotes

marchello
Posts: 81
Joined: Fri Oct 11, 2013 8:59 am

### atm - return required sum using minimum amount of 100, 50 and 20 banknotes

Hi all, this is my first Python program, please be patient to me

So, as subject says, it is atm code that should return required sum using minimum amount of 100, 50 and 20 banknotes.
Just to simplify, the input is always positive; also the input is always divisible using mentioned banknotes nominals.

My question is not Python-specific (I know that my knowledge is weak, but I will learn it better soon), it is rather looking for proper algorithm. As far as I can see, looping is not proper way here. For example, it works fine with 290 input value; but in case of 110 it takes one 100 banknote, then 10 is left which doesn't have appropriate banknote; so it should skip 100 and return one 50 plus three 20.

Code: Select all

``````def atm(value):
rest = value
result = ''
var100 = 0
var50 = 0
var20 = 0
if (rest - 100 >= 0):
while True:
rest = rest - 100
if (rest >= 0):
var100 = var100 + 1
else:
rest = rest + 100
break
if (rest - 50 >= 0):
while True:
rest = rest - 50
if (rest >= 0):
var50 = var50 + 1
else:
rest = rest + 50
break
if (rest - 20 >= 0):
while True:
rest = rest - 20
if (rest >= 0):
var20 = var20 + 1
else:
rest = rest + 20
break
result = str(var100) + ' ' + str(var50) + ' ' + str(var20)
return result

print (atm(290))
``````
Last edited by marchello on Fri Jul 10, 2020 7:24 pm, edited 1 time in total.

ghp
Posts: 1541
Joined: Wed Jun 12, 2013 12:41 pm
Location: Stuttgart Germany
Contact: Website

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

The name of the problem is "Change-making_problem".

https://en.wikipedia.org/wiki/Change-making_problem

Burngate
Posts: 6328
Joined: Thu Sep 29, 2011 4:34 pm
Contact: Website

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

Not a Python guru, so can't help with that side, but two things stand out for me.

First, there ain't no answer if you start with 10 or 30, so it might be worth checking for that before you start.

Second, why start with the largest notes and work down - the 100s, then the 50s and end with the 20s?

You'll arrive at a number of 20s, with maybe 10 left over.

If you've got 10 left, drop the 20s by two and add one 50 - that takes care of the odd 10 (you'll never need more than one 50)
else drop the 20s by five and add one 100

keep going till you've nowt left.

DougieLawson
Posts: 39551
Joined: Sun Jun 16, 2013 11:19 pm
Location: A small cave in deepest darkest Basingstoke, UK

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

Burngate wrote:
Fri Jul 10, 2020 9:13 am
Second, why start with the largest notes and work down - the 100s, then the 50s and end with the 20s?
That's the way to make change. You have to hand over the fewest number of notes and coins that way. It makes it easier for the customer assistant behind the till to make change and count it out to the customer.

You've just got to love these homework questions.
Note: Any requirement to use a crystal ball or mind reading will result in me ignoring your question.

Criticising any questions is banned on this forum.

All fake doctors are on my foes list.

HermannSW
Posts: 2765
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

In general these kind of problems can be soleved easily and efficiently by two dimensional array, here of size 3×N where N is the amount of money you want to change.
Initially A[x][y]=0 for all x,y.
A[0][y] is 0 if it cannot be paid with only 20 banknotes, otherwise it is the number of 20 banknotes.
Then iterate over all y=0..49 and set A[1][y]=A[0][y].
Then iterate over y=50..N and do: A[1][y]=min(A[1][y-50]+1,A[0][y]).
Do same with A[2] for 100 banknotes.
Finally you see minimal number of banknotes in A[2][N].
You can go back from that and determine how much 20s, 50s and 100s you need.
Runtime of algrorithm is O(3*N) which is good for any constant number of different banknote values.
Last edited by HermannSW on Fri Jul 10, 2020 10:28 am, edited 1 time in total.
https://stamm-wilbrandt.de/en/Raspberry_camera.html
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/raspiraw
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/github_repo_i420toh264

Burngate
Posts: 6328
Joined: Thu Sep 29, 2011 4:34 pm
Contact: Website

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

Yes, but ...

Barman, customer ...
The barman was adding it up as he was pulling the pints, and tells the customer what amount he needs.
The customer knows what's in her purse, hands over some amount that's convenient for her, maybe a twenty or two tens.
The barman has to take into account what change is in the till, and may ask for a couple of thruppenny bits; in return he gives her a nine-bob note, if he's got one in the till.
They're both doing stuff in the background, probably without thinking about it.

ATM ...
The customer has no input into the situation - she gets what she's given, and is grateful for what she gets.
The ATM does all its calculations before it starts to count out the notes, so it doesn't have to work "logically"
If it knows it hasn't enough seven-shekel notes to service many more potential customers, it'll find a different way to reach the "right" answer.

"Right" being far more complicated than just "fewest notes"

DougieLawson
Posts: 39551
Joined: Sun Jun 16, 2013 11:19 pm
Location: A small cave in deepest darkest Basingstoke, UK

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

Barmen are a breed apart, they'll be doing the mental arithmetic in the same way that the guy playing darts is adding up the arrows and subtracting from 501 (or the current remaining total) as each dart is played.

The ATM has counters for everything. The self-scan in Tesco is the same (it's just an ATM with a modified user interface) but they only have coin dispensers for some coins.

You take the price, subtract from the amount tendered then integer divide by each of the denomination that can be dispensed dividing the remainder each time by the next lower note or coin.

So a £8.99 bill paid with a £20 note gets £11.01 made as £10, £1, 1p. £3.12 paid with a £20 is £16.88 with £10, £5, £1, 50p, 20p, 10p, 5p, 2p, 1p. We also get into the realm of "legal tender" in §2 of the Coinage Act (1971) [that's the one that introduced decimalisation in Feb 1971] just to help complicate things http://www.legislation.gov.uk/ukpga/1971/24/section/2.

It gets easier with dollars, quarters, nickels, dimes & pennies as there are fewer steps in the iteratively divide with a remainder process.

I love the way Ireland got rid of €0.01 and €0.02 with some simple rounding rules https://www.irishtimes.com/news/consume ... -1.2397307

This is all an extremely trivial task to program in python.
Note: Any requirement to use a crystal ball or mind reading will result in me ignoring your question.

Criticising any questions is banned on this forum.

All fake doctors are on my foes list.

hippy
Posts: 8061
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

### Re: atm - return required sum using minimum amount of 100, 50 and 20 banknotes

As burngate notes a self-service till's function is not solely to give the customer the least number of coins or notes in change.

The reason is two-fold; to prevent internal holding capacity being reached and to ensure subsequent customers can be best catered for.

I would expect that last point can also apply to ATM's and there's an additional aspect of what's most useful for a customer. Two £20 and a £10 is usually better than a singe £50 note in your pocket. Ten customers withdrawing £500 as eight £50 and five £20, can be better than nine getting ten £50, with the tenth getting twenty five £20.

"It probably needs an AI solution"