Author |
Topic: Change for a Dollar (Read 899 times) |
|
mamaheshwari
Newbie
Gender: 
Posts: 2
|
 |
Change for a Dollar
« on: Dec 10th, 2004, 2:49am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Change for a Dollar
« Reply #1 on: Dec 10th, 2004, 6:30am » |
Quote Modify
|
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:
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;
}
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Change for a Dollar
« Reply #2 on: Dec 10th, 2004, 1:59pm » |
Quote Modify
|
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 
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Change for a Dollar
« Reply #3 on: Dec 10th, 2004, 8:58pm » |
Quote Modify
|
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
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Change for a Dollar
« Reply #4 on: Dec 14th, 2004, 8:49am » |
Quote Modify
|
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;
}
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Change for a Dollar
« Reply #5 on: Dec 14th, 2004, 10:56am » |
Quote Modify
|
dont you completely ignore the combinations of only having pennnies as a combination for change?
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Change for a Dollar
« Reply #6 on: Dec 14th, 2004, 10:57am » |
Quote Modify
|
Never mind! I figured... nice trick
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print