Supposedly Trivial math question.

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

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

On Tue, Oct 1, 2013 at 7:27 AM, S. Dale Morrey <sdalemorrey at> 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:, #utah on
> Unsubscribe:
> Don't fear the penguin.
> */

More information about the PLUG mailing list