7
\$\begingroup\$

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<stdio.h>
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;
}
\$\endgroup\$
  • 5
    \$\begingroup\$ (I think you are misinterpreting the results shown: as soon as consumption of more than 1 "sec" is detected, the plug is pulled.) You need a better algorithm than generating "all" digit sequences and counting the palindromes among them. \$\endgroup\$ – greybeard Nov 6 '16 at 9:36
7
\$\begingroup\$

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:

  1. The prefix length is rounded up. For the example, the prefix is 12345.
  2. 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 <stdio.h>

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 < numLength - palLength; i++)
        palPrefix /= 10;

    // Check whether the palindrome formed by palPrefix is greater than num.
    // If it is, we subtract one from palPrefix because the last palindrome
    // is not usable.
    //
    // Example 1: Is 12344321  greater than 12345678?
    // Example 2: Is 123454321 greater than 123456789?
    if (constructPalindrome(palPrefix, numLength) > num)
        palPrefix--;

    // So right now, we have palPrefix being 1234 and 12345 for the two
    // examples.  The number of palindromes less than num is close to
    // palPrefix*2.  The reason is, for each number from 1..palPrefix, you can
    // can construct two palindromes, one of odd length where the last digit
    // is not repeated, and one of even length where all digits are repeated.
    //
    // 25  -> 252    2552
    // 256 -> 25652  256652
    //
    // Starting with all these, palindromes, we adjust the count depending
    // on whether the original number had an even or odd number of digits.
    //
    // For even numLength, we are missing some palindromes, for example:
    //
    // num       = 12345678
    // palPrefix = 1234
    //
    // We can create a palindrome with prefix higher than 1234 that is still
    // less than num.  For example, choose 2345:
    //
    // 2345 -> 2345432
    //
    // So for each number from 1235..9999, we should add one to the count.
    // In other words, add 10^prefixLength - 1 - palPrefix to the count.
    //
    // For odd numLength, we have too many palindromes.  Some of the
    // palindromes already created are not usable.  For example:
    //
    // num       = 12345678
    // palPrefix = 12345
    //
    // 12345 -> 1234554321 (too big, 10 digits)
    //
    // So for all the max digit prefixes, we can only use 1 of the 2
    // palindromes.  So we should subtract some from the count.  The number we
    // need to subtract in this case is: (12345 - 9999).  In other words,
    // subtract palPrefix - (10^(prefixLength-1) - 1) prefixes.
    palPrefix *= 2;
    if (numLength & 1) {
        // Subtract off adjustment for odd length.
        int adjustment = 1;
        for (i=1;i<palLength;i++)
            adjustment *= 10;
        palPrefix -= (palPrefix/2 - adjustment + 1);
    } else {
        // Add adjustment for even length.
        int adjustment = 1;
        for (i=0;i<palLength;i++)
            adjustment *= 10;
        palPrefix += (adjustment - 1 - palPrefix/2);
    }
    return palPrefix;
}

/**
 * Constructs a palindrome from a prefix.  Examples:
 *
 * Prefix = 1234  numLength = 8, returns 12344321
 * Prefix = 12345 numLength = 9, returns 123454321
 */
static int constructPalindrome(int palPrefix, int numLength)
{
    int front = palPrefix; // Starts at 1234, builds to 12340000
    int back  = 0;         // Starts at 0   , builds to 4321

    // If the number length is odd, we do not want to repeat the last digit
    // of the prefix, so skip it here.
    if (numLength & 1)
        palPrefix /= 10;

    // For each digit in the remaining prefix, remove the last digit and
    // place it on the back of "back".  In other words, we are reversing
    // palPrefix into "back".
    while (palPrefix != 0) {
        int digit = palPrefix % 10;

        palPrefix /= 10;
        back       = back * 10 + digit;
        front     *= 10;
    }
    return front + back;
}
\$\endgroup\$
3
\$\begingroup\$

A few things that might help to improve the efficiency:

  • If a number ends with 10, it will never be a palindrome i.e 10 -> 1, 110 ->011, 1110 -> 0111 except 0. if(i%10 == 0) continue;

This should expedite a big set.

\$\endgroup\$
0
\$\begingroup\$

Is it possible to improve the runtime performance (in time) of the code?

ifpalin(int g) does O(n) loops for an n-digit number, even if an early test would indicate no chance of success.

(Let us assume 32-bit int)

Rather than form the entire palindrome of the number, (which may be impossible - consider 1,333,666,999 whose palindrome cannot be stored in 32-bit), test the most significant digit against the least. Certain to eliminate a lot of work. Palindrome tend to be rare as the number becomes larger - so assume no need to test every digit - quit early if possible.

If the most significant digit matches the least, mathematically lop off the two and try again.

Something like the below lightly tested code. (Corner case like 0, MAX may not work)

#include <limits.h>
#include <stdio.h>
const unsigned mypow10[] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000,
        10000000, 100000000, 1000000000 };

unsigned pal_test(unsigned i, unsigned p10) {
  while (p10 > 1) {
    unsigned lsdigit = i % 10;
    unsigned msdigit = i / mypow10[p10];
    if (lsdigit != msdigit) return 0;
    i = msdigit = (i % mypow10[p10]) / 10;
    p10 -= 2;
  }
  return 1;
}

unsigned pal_tests(unsigned a, unsigned b) {
  unsigned sm = 0;
  unsigned p10 = 0;
  while (a > mypow10[p10 + 1]) {
    p10++;
  }
  for (unsigned i = a; i <= b; i++) {
    if (i >= mypow10[p10 + 1]) {
      p10++;
    }
    if (pal_test(i, p10)) printf("%u\n", i);
    //printf("%u %u\n", i, pal_test(i, p10));
  }
  return sm;
}

int main(void) {
  pal_tests(9, 123);
  return 0;
}

Output

9
11
22
33
44
55
66
77
88
99
101
111
121

If if (pal_test(i, p10)) printf("%u\n", i); is commented, and ran pal_tests(1, 1000*1000*1000); code took 28 secs on my machine and counted 109998 palindromes.

\$\endgroup\$
0
\$\begingroup\$

I've tried to improve algorithmic complexity to the best of my abilities, but still have 0.0015 second overhead over passing solution (1 second).

When I read "algorithmic complexity" I immediately thought asymptotic complexity. But of course, improving asymptotic complexity would require choosing a better algorithm, and I am disinclined to believe that that's what you were trying to do. On the other hand, it's not actually what you said, either, so I guess I'm just saying that your wording could have been better.

Is it possible to improve the runtime performance (in time) of the code?

Sure. There are various minor tweaks and tricks that might shave off some cycles, but the biggest win would come from choosing a better algorithm after all. The resulting "improved code" would not look much like the present code.

In the code you've presented, you count palindromes by testing every number in the given range to determine whether it is palindromic, keeping a count of the successes. That's very straightforward, but it costs O((max - min) log max). That's not very efficient, especially if the range can be large. It would be far more efficient to compute the number of palindromes via a combinatorial approach. Consider:

  • The numbers of all one- and two-digit palindromes are 10 and 9, respectively, according to the definition implicit in your test function.

  • Every palindromic number with n > 2 digits can be constructed from a palindromic number with n - 2 digits by prepending and appending one of the non-zero digits, or similarly from one with n - 4 digits by first prepending and appending 0 and then proceeding as above, provided n == 4 or n > 5.

  • Thus every palindromic number whatever can be constructed by starting with a one- or two-digit prime and applying zero or more of the above expansion steps. Moreover, the starting palindrome and the sequence of digits with which it is expanded are uniquely characteristic of the resulting palindrome.

  • That construction can be leveraged to count palindromes up to any given bound without testing any numbers at all. Instead, one counts the number of different choices can be made in the construction to yield numbers not exceeding the bound.

For example, the number of palindromes less than of equal to 1,000,000,000 is 1 (for the palindrome 0) plus the sum of

# digits   palindrome count
  1           9             (not including 0)
  2           9
  3          10*9
  4          10*9
  5          10*10*9 
  6          10*10*9
  7          10*10*10*9
  8          10*10*10*9
  9          10*10*10*10*9
---------------------------
 any         109998

That can be computed very swiftly.

It gets a little trickier when the upper bound is not a power of 10, but note that the only tricky part is counting the in-bound palindromes with the same number of digits as the upper bound, and even that's not so bad. The count of smaller palindromes can be computed exactly as above, and can even be tabulated if you wish.

You don't need to worry about accounting for upper and lower bound at the same time. Given a function num_pals_up_to() built around the approach outlined above, you can count palindromes between a and b, inclusive, as num_pals_up_to(b) - num_pals_up_to(a - 1).

Even without tabulating or re-using anything, the asymptotic complexity of this approach is O(n(log m)2) for n ranges with upper bounds not exceeding m, which is much better than O(nm log m) for your original approach.

\$\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.