• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Here is my code for Greedy algorithm for minimum number of coins,Can you please verify my code

 
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

 
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Divyadharshini,

thanks for using code tags, but the closing tag ([/code]) should come after the code, instead of directly after the opening tag. I've repaired it. Next time, please use the "preview" button before submitting your post, to check if all is as you intended.

Then some comments:

1) your algorithm is okay! It looks a bit strange at first sight, but it works.

2) then my biggest problem I have with your code: it is a one-off code! What if you want the change for more than one input or for some other coin values? You either must re-run your code or edit it. So, why not have a method 'List<Integer> minimumNumberOfCoins(int amount, List<Integer> coins)', that you can use everywhere such a calcu;ation must be made.

3) And while we are dealing with an OO language like Java, why not have a class 'Coin', so that you can use a List<Coin>?

4) You do not need to maintain the variable 'count'. Since you put the fitting coins into a List (output), you can obtain the count by using list.size(). See the API of List.

5) If the input is, say, 3500, then you loop three times to find that the 1000 coin fits three times. That is okay, but there is a way to get that three directly. Look up the tem 'integer division'.

6) Have you tested your code? Did it function correctly? And if you look at it from a users point of view, were you okay with how the code worked?
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris
Thank you so much for the corrections. It helps me to improvise my method of writing the code.
I have tested and worked.  Thank you for reminding me to use integer division and now the code is efficient rather than looping so many times.
Thank you again.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris

If I use integer division, I need 1000,1000,1000,50 as output for 3050

so I need to loop 3 counts equal to remainder and add values to output,

Am I right in implementing Integer Division?
 
Piet Souris
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would certainly use integer division, but I must say I like your algorithm, with its loops. I found it nice and original.

So, we could add the 1000 coin 3 times in the output list. But, wouldn't it be better to create a Map<Coin, Integer> as a frequency map, so that you can do:

If you have a Coin class, as I suggested, you could have the elegant loop:




Edit: I forgot to mention that, in order to get the minimum of coins, it is required to have your List<Coin> sorted, from high to low. In the code in your opening post you had this List correctly filled. But it seems wise not to rely on that, so I would recommend to sort your coin list before using it.
 
Divyadharshini Karthikeyan
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Souris
thank you ,now I understood the logic.

 
Piet Souris
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome!

Do show us your latest code, if you like.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!