You missed one thing.

You can further divide those n/2 , n/3 , n/4 coins to maximise profit.

Eg-

Lets say we have 24.

We divide it into 12 , 8, 6.

As you see in sample case, we can again divide 12 to obtain 13. You have to go till that step when exchanging coins for notes no longer gets you profit. Its not a one time operation.

EDIT-

There, solved the Q (although not by the required method i guess)

My solution is here

Basically what i did was to use recursion. I created a function “change()” to get the answer. For a value, return the max(n, change(n/2)+change(n/3)+change(n/4))

Since we will be doing lots of unnecessary computations, its better to store the values (i.e. use dynamic programming).

But an array of 10^9 cant be created. I did by using an array of 10^8 (for values b/w 10^8-10^9, its simple brute force recursion, while values less than 10^8 are stored). I think some other data structure ahd to be sued, of which i am unaware of.

Get back to me if you have doubts.