Supposedly Trivial math question.

Lonnie Olson lists at kittypee.com
Tue Oct 1 10:23:55 MDT 2013

```Here's my attempt w/o any real fancy base2 stuff.

http://pastebin.com/nSd3h5qH

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.
> */
```