patterncppModerate

Optimisation of palindrome

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

palindromeoptimisationstackoverflow

Problem

My program takes as first input the number of test cases, n. For the following n inputs, I output the smallest positive integer that has to be added to the input to make the input a numeric palindrome. If the input is already a palindrome the output shall be zero.

I have a problem with the performance, the algorithm is correct but I get get time limit exceeded. The input number is in the range \$[1, 1000000]\$.

#include 
#include 
#include 
using namespace std;

extern bool isPal(const int &number) __attribute__((fastcall)); 

bool isPal(const int &number)
{
    char buffer[6];
    sprintf(buffer,"%i",number);
    const string x = buffer;
    for(int i=0, end = x.size()-1;i<end;i++,end--)
        if(x[i]!=x[end])
        return false;
    return true;
}

int main()
{
    int n, number, counter, t;
    scanf("%i",&n);
    while(n--)
    {
        counter = 0;
        scanf("%i",&number);
        t = number+counter;
        while(!isPal(t))
        {
            ++counter;
            t = number+counter;
        }
        printf("%i\n",counter);
    }
    return 0;
}

Please help me optimise the above code.

Solution

Comments on the code as it is

This:

__attribute__((fastcall))

will not improve your performance, as the culprit is the algorithm not the compiler. If you really want to tell the compiler to optimize your code harder, you can try inline instead.

This forward declaration:

extern bool isPal(const int &number) __attribute__((fastcall));

is unnecessary as the function body directly follows the forward declaration.

Looking at the isPal function the name could have been better. I would suggest isPalindrome.

bool isPal(const int &number)
{
    char buffer[6];
    sprintf(buffer,"%i",number);
    const string x = buffer;
    for(int i=0, end = x.size()-1;i<end;i++,end--)
        if(x[i]!=x[end])
        return false;
    return true;
}

Unless you need to modify the argument, always take simple types by value; so const int& number should be int number.

The input range is \$[0,1000000]\$ so your buffer is too small it needs to be at least 7 + 1 (for the null terminator).

The use of sprintf is discouraged, please prefer snprintf instead. You might want to consider stringstream for type conversion but I'll leave that up to you.

The variable const string x is unnecessary, simply use strlen from ` instead.




You really should put some white spaces in there as the code is hard to read as it is.

Always prefer to use curly braces ({}) on control statements. Your missing indentation on the return false statement is confusing.

Also you can do without the end variable, but that's up to taste. But I will leave it there.




Fixing the above, your function should look like:

bool isPalindrome(int number)
{
    char buffer[8];
    snprintf(buffer, 8, "%i", number);
    int len = strlen(buffer);
    for(int i = 0, end = len - 1; i < end; i++, end--){
        if(buffer[i] != buffer[end]){
            return false;
        }
    }
    return true;
}


Now looking at your

main()

 function.

Always prefer to declare your variables in the smallest possible scope. This makes the code easier to read. This means that counter, number and t should be declared inside of the loop body.

You're using C-style IO in a C++ program, this is not recommended. Instead you should use C++ streams cin and cout`.

Again you could use some more white spaces.

The fixed code:

int main()
{
    int n;
    cin >> n;;
    while(n--)
    {
        int counter = 0;
        int number;
        cin >> number;
        int t = number + counter;
        while(!isPal(t))
        {
            ++counter;
            t = number + counter;
        }
        cout << counter << endl;
    }
    return 0;
}

Data handling improvements

You are formatting the input to a string to check if it is a palindrome. This is quite unnecessary. To test if an integer is a numeric palindrome, you need to count the number of digits in the number, then extract and flip the digits in the top half and compare them to the bottom half. Like this:

int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

int countDigits(int value){
  int digits = 0;
  while(value != 0){
    value /= 10;
    digits++;
  }
  return digits;
}

int flipDigits(int value){
  int ans = 0;
  while(value){
    ans *= 10;
    ans += value % 10;
    value /= 10;
  }
  return ans;
}

int isPalindrome(int value){
  int digits = countDigits(value);
  int ten_pow_digits_2 = ipow(10, digits/2);
  int high_digits = value / ten_pow_digits_2;
  if(digits%2){
    high_digits /= 10;
  }
  int low_digits = value % ten_pow_digits_2;

  return flipDigits(high_digits) == low_digits;
}

This will check if the number is a palindrome without formatting to a string and will be faster. However we can do better by improving the algorithm.

Algorithmic improvements

I'm not going to describe the correct algorithm here as @outoftime has already done so in his answer. Instead I'm going to provide a different implementation of the same algorithm with less code that doesn't abuse inheritance of the standard containers. You can find such improvements as predefined values and so on.

#include 

constexpr int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp > n;

  while(n--){
    int input;
    std::cin >> input;
    std::cout << calcPalindromeDeficiency(input) << std::endl;
  }
  return 0;
}

I find it more elegant to not convert to string when handling numbers.

Code Snippets

bool isPal(const int &number)
{
    char buffer[6];
    sprintf(buffer,"%i",number);
    const string x = buffer;
    for(int i=0, end = x.size()-1;i<end;i++,end--)
        if(x[i]!=x[end])
        return false;
    return true;
}

bool isPalindrome(int number)
{
    char buffer[8];
    snprintf(buffer, 8, "%i", number);
    int len = strlen(buffer);
    for(int i = 0, end = len - 1; i < end; i++, end--){
        if(buffer[i] != buffer[end]){
            return false;
        }
    }
    return true;
}

int main()
{
    int n;
    cin >> n;;
    while(n--)
    {
        int counter = 0;
        int number;
        cin >> number;
        int t = number + counter;
        while(!isPal(t))
        {
            ++counter;
            t = number + counter;
        }
        cout << counter << endl;
    }
    return 0;
}

int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

int countDigits(int value){
  int digits = 0;
  while(value != 0){
    value /= 10;
    digits++;
  }
  return digits;
}

int flipDigits(int value){
  int ans = 0;
  while(value){
    ans *= 10;
    ans += value % 10;
    value /= 10;
  }
  return ans;
}

int isPalindrome(int value){
  int digits = countDigits(value);
  int ten_pow_digits_2 = ipow(10, digits/2);
  int high_digits = value / ten_pow_digits_2;
  if(digits%2){
    high_digits /= 10;
  }
  int low_digits = value % ten_pow_digits_2;

  return flipDigits(high_digits) == low_digits;
}

#include <iostream>

constexpr int64_t ipow(int64_t base, int exp, int64_t result = 1) {
  return exp < 1 ? result : ipow(base*base, exp/2, (exp % 2) ? result*base : result);
}

// This covers the range of int.
const int pow10[]{ipow(10,0), ipow(10,1), ipow(10,2), ipow(10,3), 
    ipow(10,4), ipow(10,5), ipow(10,6), ipow(10,7), ipow(10,8), ipow(10,9) };

int countDigits(int value){
  int digits = 0;
  while(value != 0){
    value /= 10;
    digits++;
  }
  return digits;
}

int getDigit(int value, int digit){
  int place = pow10[digit];
  return (value/place) % 10;
}

int calcPalindromeDeficiency(int value){
  const int digits = countDigits(value);
  int digit = 0;
  int ans = 0;
  while(digit != (digits+1)/2){
    int top_digit = getDigit(value, digits - digit - 1);
    int bottom_digit = getDigit(value, digit);
    int to_add = ((10 + top_digit - bottom_digit)%10)*pow10[digit];
    ans += to_add;
    value += to_add;
    if(getDigit(value, digits - digit - 1) == getDigit(value, digit)){
      digit++;
    }
  }
  return ans;
}

int main(){
  int n;
  std::cin >> n;

  while(n--){
    int input;
    std::cin >> input;
    std::cout << calcPalindromeDeficiency(input) << std::endl;
  }
  return 0;
}

Context

StackExchange Code Review Q#64173, answer score: 12

Revisions (0)

No revisions yet.