How to solve Bytelandian gold coin ?

general
, ,
1

question

This is my solution to the problem. Can anyone tell me what is wrong with it ?

solution

2

You’re not attempting to convert the coins that you get from converting the first one (and so on). In the first example below:
40 \to 20 + 13 + 10 \to (10 + 6 + 5) + 13 + 10 = 44

Some more test cases for you:

40
50
60
400

output:

44
57
68
533
3

@joffan
this is my code


[1]


  [1]: https://www.codechef.com/viewsolution/21210211

Approach i used is: if (n<12) max_value=n, else: max_value = calc_max(n/2) + calc_max(n/3) + calc_max(n/4)
along with saving the entries in HashMap with each value of n

Test cases mentioned above have passed,
but the problem is when I submit this code, it gives me TLE.

I ran the code in my local system, gave output of 4243218150, for input: 1000000000 in around 30 seconds.

Can you or anyone help me out here ?
4

no worries, there was a minor issue, i was not returning from recursive call, when getting value from map, its solved now