Coin Exchange TLE

#1

Code: https://ide.codingblocks.com/s/106454
I’m getting TLE for first test case and Wrong answer for the second one. Please check

#2

@tomarvikas738
Even though your code seems right for Bottom Up Approach , I regret to inform you that this is one of those problem which simply CANNOT be solved using Bottom Up Approach. You have to use Top Down Approach for this.
The reason for this is , as you can see in the problem constraints
0 <= n <= 1 000 000 000
N can be as large as 10^9. Bottom Up DP requires you to create a DP array of size N+1. We simply cannot create an array of such a large size under any circumstance in any way in C++. It is just not permitted by the compiler.
We use modified Top Down Approach to solve this problem. We make a DP array as large as we can , as large as the compiler permits. Let’s call this size as MAX.
We use DP to store to compute any values lower than MAX and when we get a recursive call for any value larger than MAX , we do not either check for this in our DP array , or even try to store it. We compute it … and return it , without storing it.
For any value lower than MAX , we check if it stored in DP array , compute if not stored and store it before returning it.
Basically we are taking advantage of the recursion involved in Top Down Approach to solve this otherwise impossible problem. DP will handle all values lower than MAX. Recursion will handle the rest.
Try the Top Down Approach as I have suggested and let me know if you face any problems.

2 Likes
#3

Thanks Tarun, for such an insightful explanation!

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.