Bytelandian gold coins using c++ - TLE

help
1

hi i recently solved bytelandian problem(link below)

my solution(below) which exeeds the time limit

#include

using namespace std;
long long int fun(long long int n)
{
long long int a=(n/3)+(n/4)+(n/2);
if(a>n)
return (fun(n/3)+fun(n/4)+fun(n/2));
return (n);
}
int main()
{
long long int n;
while(cin>>n)
{

    cout<<fun(n)<<"\n";
}
return 0;

}

ideal solution
#include
#include
#include
#include
using namespace std;

long long int fun(long long int n,long long int *m)
{
if(n==0 || n==1)
return n;
if(m[n]!=0)
return m[n];
m[n]=max(n,fun(n/2,m)+fun(n/3,m)+fun(n/4,m));
return m[n];

}
int main() {
long long int n;
while(cin>>n)
{
long long int *m=new long long int[n+1];
cout<<fun(n,m)<<“\n”;
}
// your code goes here
return 0;
}

can you plz tell me why my ans is taking more time

2

First of all correct solution should be:
use the following edit:
long long int a=fun(n/3)+fun(n/4)+fun(n/2);
instead of a=n/3+n/4+n/2;

and lastly:
if(a>n)
return a;
return n;

but the above will still show tle because of recursion.
that’s why the last code you pasted is using Dynamic Programming to save time.