# MINIMUM NUMBER OS STEPS SPOJ TLE

LINK TO QUESTION - > http://www.spoj.com/problems/MST1/

``````#include<cstdio>
#define M 20000007
typedef int ull;

inline ull mi(ull a,ull b)
{
if(a>b)
return b;
else
return a;
}
int main()
{

int t;
scanf("%d",&t);
while(t--)
{
ull n;
scanf("%d",&n);
ull *dp=new ull[n+1];
dp[1]=0;
for(ull i=2;i<=n;i++)
{

dp[i]=dp[i-1]+1;
if(i%2==0)
{
dp[i]=mi(dp[i],1+dp[i/2]);
}

if(i%3==0)
{
dp[i]=mi(dp[i],1+dp[i/3]);
}
}
printf("%d\n",dp[n]);

}
return 0;
}
``````

here is my solution
i am using dp to solve this
still getting tle
can you please tell me what should be done to optimize this code

Why are you calculating the values repeatedly? For every input value of n, you are traversing the loop 2 to n. Lets say first input was 7. In the first iteration(corresponding to test cases), you find values of all dp[1…7]. Next input was lets say, 15, so you are again calculating dp[1…15] where dp[1…7] was already there. Why do this repetitive work? Pre-calculate the values for all i belonging to set [1,MAX] where MAX is 20000000. Now, for every value of n, just output dp[n], so, constant time. Computation time(Processing time is O(n)).

Refer my solution here or on the same post on quora you A2A.