# Supposedly Trivial math question.

Tue Oct 1 10:24:22 MDT 2013

```Here is a php solution

<?
// Basically using successive subtraction, which as it turns out is
division.  Code could be faster, but this is probably easier to understand

\$paidsWith = 1300.00;
\$owes = 123.45;
\$change = \$paidsWith - \$owes;

\$result = array();
\$bills = array(100, 50, 10, 5, 1, 0.50, 0.25, 0.05, 0.01); // Sorted
bcscale(5); // Ten thousands

while(\$change > 0){
foreach(\$bills as \$bill){
if(bccomp(\$change, \$bill) >= 0){
echo "\$change - \$bill\n";
\$change = bcsub(\$change, \$bill);
\$result["\$bill"]++;
break;
}
}
}
foreach(\$result as \$bill => \$number){
echo \$number . '-' . \$bill . 's ';
}
echo "\n";

[adam at rivendale /tmp:Tue 10:22:58]\$ php bills.php
1176.55 - 100
1076.55000 - 100
976.55000 - 100
876.55000 - 100
776.55000 - 100
676.55000 - 100
576.55000 - 100
476.55000 - 100
376.55000 - 100
276.55000 - 100
176.55000 - 100
76.55000 - 50
26.55000 - 10
16.55000 - 10
6.55000 - 5
1.55000 - 1
0.55000 - 0.5
0.05000 - 0.05
11-100s 1-50s 2-10s 1-5s 1-1s 1-0.5s 1-0.05s

On Tue, Oct 1, 2013 at 7:27 AM, S. Dale Morrey <sdalemorrey at gmail.com>wrote:

> This was posed to me at an interview and stupidly I got nervous and I
> choked on it.  Now it's been burning in my mind and I'm trying to solve
> it.  It seems simple enough, but for some reason I'm hitting a mental block
> here.
>
> Imagine you're writing a program for a clerk making change.  The currency
> is purely a single base, i.e. base 10, base 2 etc, but the base is
> arbitrary.
>
> The clerk has to give a customer the exact change to the penny.
>
> give change in the following scenario
>
> Customer owes \$123.45
> Customer pays with \$1,300. (not a typo and I have no idea why they're
> overpaying by so much).
>
> You must return a single string telling the clerk how many of each
> denomination to give in any arbitrary integer base.  You can assume that
> the smallest fractional component is a whole unit i.e. 123.45 would be 5
> ones, 4 tens, 3 hundreds, 2 thousands and 1 ten thousand.  You should not
> assume any upper limit on individual bill size (ala Zimbabwe dollars).
>
> You can assume that the clerk has an infinite supply of each bill, but
> there are bonus points if the function can cope (i.e. find an alternate
> output), if there is an insufficient quantity on hand of any particular
> bill or bills.
>
> You do not need to wordize the bills, that is the string can look like...
>
> 5-1's, 4-10s, 3-100s etc. instead of 5 ones, 4 tens, 3 hundreds.
>
> For expediency you may return the string in high order or low order
> notation i.e.
> 3-100s, 4-10s, 5-1s is also acceptable.
>
> As a lifeline, you are allowed to simply pick any arbitrary base and
> restrict your answer to only that base.  You can also do it in any language
> you feel would work best but you may not use any library which is not
> generally accepted as core to the language you pick.
>
> My solution turned into a mess on the whiteboard, long division by hand was
> never was my strong suit I guess.  Looks like in my old age, place value
> has begun to fall out of my head as well.
>
> I believe the correct solution involves finding the high bit and dividing
> recursively, but something tells me there is a better way.
>
> Have Fun!
>
> /*
> PLUG: http://plug.org, #utah on irc.freenode.net
> Unsubscribe: http://plug.org/mailman/options/plug
> Don't fear the penguin.
> */
>
```