wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Change for a Dollar
        
(Message started by: mamaheshwari on Dec 10^th, 2004, 2:49am)

Title: Change for a Dollar
Post by mamaheshwari on Dec 10^th, 2004, 2:49am

Microsoft Interview Question
Write a progrm that find outs the number of ways to get change for n Dollars using coins of 1/100, 1/20, 1/10, 1/4, 1/2 dollar.

Title: Re: Change for a Dollar
Post by Grimbal on Dec 10^th, 2004, 6:30am

I guess the catch is
1. If you choose to use Java, it is bad
2. If you represent dollars using floats or doubles (for the cents) it is also bad.

Anyway, I would go along these lines:
[hide]
int change(int n)
{
int count = 0;
int a, b, c, d, e;

for( a=100*n ; a>=0 ; a-=50)
for( b=a ; b>=0 ; b-=25)
for( c=b ; c>=0 ; c-=10)
for( d=c ; d>=0 ; d-=5)
for( e=d ; e>=0 ; e-=2)
count++;

return count;
}
[/hide]

Title: Re: Change for a Dollar
Post by John_Gaughan on Dec 10^th, 2004, 1:59pm

Grimbal,

Why do you have a "2" in that last for loop?

Also, I think that line is totally unnecessary anyway. Once you get to nickels, you already know there is one arrangement of pennies to make up the final difference ;)

Title: Re: Change for a Dollar
Post by puzzlecracker on Dec 10^th, 2004, 8:58pm

I don't see how this is going to work!!!!

Is the question to find a number of ways to change n dollors using mentioned metric???

Title: Re: Change for a Dollar
Post by Grimbal on Dec 14^th, 2004, 8:49am

Oops, sorry, you are right. I didn't realize there is no 2c coin in the list. In Switzerland we have 10c, 5c, 2c, 1c. And yes, I did not include the 1c coin since there is a single way to make up the rest with 1c coins.
The version 2.0 of my program:

int change(int n)
{
int count = 0;
int a, b, c, d;

for( a=100*n ; a>=0 ; a-=50)
for( b=a ; b>=0 ; b-=25)
for( c=b ; c>=0 ; c-=10)
for( d=c ; d>=0 ; d-=5)
count++;

return count;
}

Title: Re: Change for a Dollar
Post by puzzlecracker on Dec 14^th, 2004, 10:56am

dont you completely ignore the combinations of only having pennnies as a combination for change?

Title: Re: Change for a Dollar
Post by puzzlecracker on Dec 14^th, 2004, 10:57am

Never mind! I figured... nice trick