Hi,

I’m solving problem_statement but getting wrong answer, so I saw solution but didn’t get why they are creating two cases (less than 100001 and greater than this) already submitted answer please help.

Link of my solution is my_solution

Hi,

I’m solving problem_statement but getting wrong answer, so I saw solution but didn’t get why they are creating two cases (less than 100001 and greater than this) already submitted answer please help.

Link of my solution is my_solution

After you split the coin into a = n/2 , b = n/3 , c = n/4, you need to check if you can split a , b or c into three parts and so on so that you gain maximum answer. You are doing it only once. Try a recursive approach. This is good problem to learn about recursion.

P.S : The submitted solution you are referring to also uses recursion.

Hey @jpriya2903,

This is a pretty standard problem on starting with DP, the reason why they are creating two cases is that the array of size greater than this cannot be created and to reduce the time complexity. if the answer is already calculated than it can give an output of queries lesser than 10^6 in O(1) as they are stored but for queries greater than 10^6 we cannot store them so we have to compute them again and again.

Here is my code, with some what different approach.

Hope this helps!