I am trying to solve Bishops problem on SPOJ. I am getting a TLE. There are actually 3 for loops effectively which on maximum runs for 100 times, even though TLE!!! Can some one point out inefficient part of the code?
Edit: I optimized the code as shown below. This time no function calls etc… but TLE!! I have solved this question using Java, Python. I really want to implement this using C++. Any help would be appreciated. Thanks!!
/Earlier code/
#include #define si(a) scanf("%d",&a) #define nl printf("\n") #define ULL unsigned long long //set sx, sy; using namespace std; int A[101]; char ans[100]; int l; void done(int i){ if(!A[i]){ A[i]=9; ans[l-i-1]=A[i]+'0'; done(i+1); } else { A[i]--; ans[l-i-1]=A[i]+'0'; } } int main() { int i; char P[100]={0}; while(scanf("%s",P)!=0){ int c=0,x; memset(A,0,100); memset(ans,0,100); l=strlen(P); for(i=l-1;i>=0;i--){ A[l-i-1]=P[i]-'0'; } for(i=0;i=2){ A[0]=A[0]-2; ans[l-1]=A[0]+'0'; } else { A[0]=A[0]+10-2; ans[l-1]=A[0]+'0'; done(1); } if(c)printf("%d",c); puts(ans); nl; } return 0; } /*optimized code*/ #include #define si(a) scanf("%d",&a) //set sx, sy; using namespace std; int A[101]; char ans[100]; int l; int main() { int i; char P[100]={0}; while(scanf("%s",P)!=0){ int c=0,x; memset(A,0,100); memset(ans,0,100); l=strlen(P); for(i=l-1;i>=0;i--){ A[l-i-1]=P[i]-'0'; } A[l-1]--; for(i=0;i<l;i++){ x=A[i]; if(i<l-1)x+=9; x=2*x+c; A[i]=x%10; ans[l-i-1]=A[i]+'0'; c=x/10; } if(c)printf("%d",c); puts(ans); printf("\n"); } return 0; }