Varun Gokulnath

Greenhorn

Posts: 13

posted 2 years ago

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.

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

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

posted 2 years ago

- 1

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.

.

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

posted 2 years ago

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:

Thanks

Varun

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

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. |