Calculate the number of palindrome numbers in the given ranges

I've written a program that calculates all of the palindrome numbers in the given range, but the code is slightly slower than needed. I've tried to improve algorithmic complexity to the best of my abilities, but still overhead over passing solution (1 second). Is it possible to improve the runtime performance (in time) of the code?


\$n\$ - number of tests


\$a, b\$ - range in which I need to calculate number of palindromes

Here is the code:

#include
int ifpalin(int g)
{
    int rev=0;
    int tmp=g;
    while(tmp>0)
    {
        rev=rev*10+(tmp%10);
        tmp=tmp/10;
    }
    if(rev==g)
        return 1;
    else
        return 0;
}
int findpalin(int a1,int b1)
{
    int sm=0;
    for(int i=a1;i<=b1;i++)
    {
      if  (ifpalin(i)==1)
        sm++;
    }
    printf("%d",sm);
    printf("\n");
    return 0;
}
int main()
{
int a,b,n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        scanf("%d",&b);
        findpalin(a,b);
    }
    return 0;
}

Need new algorithm

The current algorithm you are using takes \$O(n \log m)\$ time, where \$n\$ is the size of the range and \$m\$ is the larger end of the range. For example, if you are trying to find the number of palindromes between 1 and 1000, you iterate through all 1000 numbers (\$n\$) and for each number you do a palindrome check that iterates through the 3 digits of the number (\$\log m\$). Given a large range, such as 1..1000000000, your program will be iterating for a long time.

Can be done in \$O(\log m)\$ time

This problem can actually be done in logarithmic time. First, change the problem to finding the number of palindromic numbers between 1 and n. Then the answer to the actual problem will be num(b) - num(a-1).

Now, to find how many palindromes there are between 1 and n, there is a trick you can use. You don't have to count/find actual palindromes. You can just look at the front half of the given number to get an estimate of the number of palindromes.

Example for even number of digits

How many palindromes are there between 1 and 12345678?

If you take the front half ("prefix") of the number, i.e. 1234, you can use that to estimate the number of palindromes. Each number between 1 and 1234 can "generate" two palindromes: one with the last digit not repeated (making an odd number of digits), and one with all digits repeated (making an even number of digits).

Example: take the number 25. This number can generate two palindromic numbers:

25 -> 252   (the last digit 5 is not repeated = odd number of digits)
25 -> 2552  (all digits repeated = even number of digits)

If you take all the numbers between 1 and 1234, you can generate 1234*2 palindromes this way. You can also easily prove that all of the generated palindromes are less than 12345678.

However, there are also some palindromes that are missing. These are generated by prefixes greater than 1234. For each of the prefixes from 1235..9999, there is another palindrome that should be counted. For example, take the number 2345.

2345 -> 2345432  (should be counted)
2345 -> 23455432 (too large)

So in addition to the prefix*2 palindromes already counted, we need to add 10^prefixLength - prefix - 1 extra palindromes. The final answer is:

number of palindromes = prefix * 2 + 10^prefixLength - prefix - 1

Example for odd number of digits

How many palindromes are there between 1 and 123456789?

The answer for an odd length number is similar for an even length number. I won't go through the whole proof, but here are the differences:

• The prefix length is rounded up. For the example, the prefix is 12345.

• Some of the prefix*2 palindromes generated are not valid because they are larger than the original number. All of the prefixes from 10000..12345 generate an extra prefix that is too large. So there is an adjustment to subtract from the count of prefix - 10^(prefixLength-1) + 1.

The final answer for an odd length is:

number of palindromes = prefix * 2 - prefix + 10^(prefixLength-1) - 1

Final adjustment

I skipped one detail in all of the above. Sometimes you need to subtract one from the prefix because the palindrome it generates is less than the original number. For example, for 12345678, 1234 is the correct prefix to use because 12344321 is less than 12345678. But if the original number were 12340000, then 1234 would be too high because 12344321 is greater than 12340000. So you would use 1233 instead.

Example program

Here is a program that utilizes the method above to solve the problem in \$O(\log m)\$ time:

```
// Counts the number of palindromic numbers between two given numbers a and b.
//
// 121 is palindromic, 123 is not.
//
// Input is "n", the number of tests, and then n pairs of "a b".

#include

static int numPalindrome(int num);
static int constructPalindrome(int palPrefix, int numLength);

int main(void)
{
int a = 0;
int b = 0;
int n = 0;

scanf("%d", &n);
while (n-- > 0) {
scanf("%d %d", &a, &b);
printf("%d\n", numPalindrome(b) - numPalindrome(a-1));
}
return 0;
}

// Returns the number of palindromes between 1 and num. If the input is 0,
// this function will return 0.
static int numPalindrome(int num)
{
int numLength = 0;
int palLength = 0;
int palPrefix = 0;
int temp = 0;
int i = 0;

// Example 1: num = 12345678
// Example 2: num = 123456789

// Find the length of the number, in digits. Examples: 8 and 9
for (numLength=0, temp = num; temp != 0; temp /= 10)
numLength++;

// Find the palindrome prefix, which is the front half of the number,
// rounding up the length.
//
// Examples: palLength = 4 and 5
// palPrefix = 1234 and 12345
palLength = (numLength+1) / 2;
palPrefix = num;
for (i=0; i num)
palPrefix--;

// So right now, we have palPrefix being 1234 and 12345 for the two
// examples. The nu

StackExchange Code Review Q#146288, answer score: 8