• Post Reply Bookmark Topic Watch Topic
  • New Topic

Different ways to give change for various denominations  RSS feed

 
Varun Gokulnath
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I am currently preparing for a technical interview. I've been solving questions from the book "Cracking the coding interview". I am currently stuck on one of the problems.
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.


I know that the question asks for the different combinations of the coins that make up the value = n. But, I wanted to test my understanding of recursion and wrote some code to print all possible combintions in the solution.



When I saw the output I realized my mistake. The algorithm uses the logic that makes it see two quarters as different and two dimes as different and so on.

While brainstorming to fix this issue, I thought of using a Set to remove duplicates but still seems wasteful as I should not even be generating them.

Any pointers on how I could fix this algorithm are greatly appreciated.

Thanks
Varun
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is a fairly simple rule you can apply. You might have to pass more information in your recursive calls though.

The problem with your algorithm as you have pointed out is that
10 + 10 + 5 , 10 + 5 + 10 and 5 + 10 + 10 get reported as three different solutions, when they are really only one - 2x10 + 1x5

My suggestion: Add a variable to your recursive call so you can see the ORDER of the coins added. A String would do well enough.
Print that out with each answer so you can see the order of coins in the solution.

Once you see that output, you should be able to spot a fairly simple rule you can apply that can chop out whole branches of the search tree you would otherwise visit.


.

 
Varun Gokulnath
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stefan,

Your suggestion about using the order is spot-on. Thank you for your help.

I used an additional parameter to keep track of the item/coin that I previously used. I am posting the full code below, to help others who want to know how I solved the issue.


This gives the correct 13 combinations below:


25s 1 10s 0 5s 0 1s 0 order 25
25s 0 10s 2 5s 1 1s 0 order 10 10 5
25s 0 10s 2 5s 0 1s 5 order 10 10 1 1 1 1 1
25s 0 10s 1 5s 3 1s 0 order 10 5 5 5
25s 0 10s 1 5s 2 1s 5 order 10 5 5 1 1 1 1 1
25s 0 10s 1 5s 1 1s 10 order 10 5 1 1 1 1 1 1 1 1 1 1
25s 0 10s 1 5s 0 1s 15 order 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 5 1s 0 order 5 5 5 5 5
25s 0 10s 0 5s 4 1s 5 order 5 5 5 5 1 1 1 1 1
25s 0 10s 0 5s 3 1s 10 order 5 5 5 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 2 1s 15 order 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 1 1s 20 order 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25s 0 10s 0 5s 0 1s 25 order 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1



Thanks
Varun
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!