You are not logged in. Please login at to post your questions!


doubt-any help????

solution link: problem link: what is wrong with the solution?

asked 08 Jun '17, 16:46

viralivora's gravatar image

accept rate: 14%

You are doing a basic error.

Lets say the coin value is X.

We see that X/2 +X/3+X/4 is greater than X. Good! But we can further break that X/2 , X/3 and X/4 into even smaller pieces such that we get more coins.

Eg- lets take X=100

We get coin 50,33,25.

Now we can divide 50 to- 25, 16,12.

Similarly we can do to 33 and 25.

Meaning, you have to do the process on and on, until dividing into smaller coins yields no profit. (Maths will show that this for X<=12 , we get no profit)

What you will ahve to do is recursion +memonisation.

But how will you store the values? (As such large array isnt possible)

In C++, there is a data structure called maps. Its speciality is that, you can define the "key" by which you will access the element. So when you say map[x]=x, it will store x and make a key "x" to access it. (Do some research on it if needed)


You can just store results for values <=10^7 or 10^8 in array and still happily solve the question. Get back to me if doubt exists.


answered 08 Jun '17, 17:45

vijju123's gravatar image

5★vijju123 ♦
accept rate: 19%

This is a basic dp question and here is my accepted solution

if you still have any doubt then feel free to comment


answered 08 Jun '17, 16:52

hruday968's gravatar image

accept rate: 14%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 08 Jun '17, 16:46

question was seen: 295 times

last updated: 08 Jun '17, 17:45