1
\$\begingroup\$

This is codechef beginner problem. How I can make it efficient, It is taking 2.09 sec while time limit is 2.0764 secs.

Problem is: For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

https://www.codechef.com/problems/PALIN

#include<iostream>
using namespace std;

long int reverse_num(long int n){
  long int reversenumber=0,remainder1;
    while(n != 0){
    remainder1 = n%10;
    reversenumber = (reversenumber*10)+remainder1;
    n /= 10;   
}
return reversenumber;
}

int main(){

int T;
cin>>T;

while(T--){

long int n,reversenum;
bool chek;
cin>>n;
n = n+1;
bool flag = false;
while(!flag){

    reversenum = reverse_num(n);
    (n == reversenum) ? flag = true : flag = false;
    n++;
}
cout<<reversenum;     
}
return 0;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please include the description of the programming challenge to increase odds of receiving more detailed answers. If you have a problem of time-limit-exceeded you can add the corresponding tag to your question. \$\endgroup\$ Jan 31 at 10:45
  • \$\begingroup\$ a given positive integer K of not more than 1000000 digits: such a number in a long int ??? \$\endgroup\$
    – Damien
    Feb 1 at 14:32
2
\$\begingroup\$

You can simplify the loop in main. flag is unnecessary. Just use an infinite loop with a break statement. Also, because you know that any number with a zero as the last digit won't be a palindrome, you can skip those.

Putting those together, you get:

for (;;) {
    reversenum = reverse_num(n);
    if (reversenum == n) break;
    ++n;
    if (n % 10 == 0) ++n;
}

This will skip about 10% of the possible candidates.

An additional possible improvement (which is left as an exercise for the reader) involves determining what the largest digit of n is, then only looking at numbers that have a last digit that matches. This would allow you to skip 90% of the possible candidates with little additional overhead.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.