The Next Palindrome - CodeChef

Question

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;
}

Answer 1

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.