Finding n-th smallest Palindrome number (where 1<=n<=5000 and the palindrome number must have odd number of digits)

Question

I am working on this code from 3 days from a website called Codechef, the code compiles, executes and even give correct results but my code is taking 1.01 sec, but the time limit for question is 1sec, I have tried various ways but neither of them is giving a result that can work within 1 sec.

The question is about finding n-th smallest palindrome number, say n=9, then another k-th smallest palindrome number, say k=13, then I have to do this :- [(nth)^(nth+1)]* [(nth)^(nth+2)].......[(nth) ^(kth)], where nth+1 refers to 10th smallest palindrome number, nth+2 refers to 11th smallest palindrome number and so on , {T, L and R} are the inputs , L and R are less than or equal to 5(10^3), as the output will be very large so the judge wants the answer as output modulo 10^9+7 , link of the question - https://www.codechef.com/JULY21C/problems/CHEFORA

#include <stdio.h>

int main(void) {
    int T;
    scanf("%d",&T);
    while(T--){
            int arr[5001]={0};
            long int product=1;
            int j=0,big=1000000007;
            int L,R,sumR=0,sum2=0;
            scanf("%d %d",&L,&R);
            int n,p,k,h;
            
            for(n=1;n<10;n++){
                arr[j++]=n;
                if(sumR==R-1) break;
                sumR++;
            }
                
            for(n=1;n<10;n++){
                for(p=0;p<10;p++){
                  arr[j++]=n*100+p*10+n;
                  if(sumR==R-1) break;
                  sumR++;
                }if(sumR==R-1) break;
            }
            for(n=1;n<10;n++){
               for(p=0;p<10;p++){
                 for(k=0;k<10;k++){
                   arr[j++]=n*10000+p*1000+k*100+p*10+n;
                   if(sumR==R-1) break;
                   sumR++;
                 }if(sumR==R-1) break;
               }if(sumR==R-1) break;
            }
            
            for(n=1;n<10;n++){
               for(p=0;p<10;p++){
                  for(k=0;k<10;k++){
                    for(h=0;h<10;h++){
                    arr[j++]=n*1000000+p*100000+k*10000+h*1000+k*100+p*10+n;
                     if(sumR==R-1) break;
                     sumR++;
                    }if(sumR==R-1) break;
                  }if(sumR==R-1) break;
               }if(sumR==R-1) break;
            }
            for(j=L+1;j<=R;j++)
                sum2+=arr[j-1];
                
            for(j=1;j<=sum2;j++)
                product=(product*arr[L-1])%big;
                
            printf("%ld\n",product);
        }
        return 0;
    }

Answer 1

The obvious issue with this code is the lack of structure. There are two main computations, given that we've already spotted that we can add all the exponents and perform a single exponentiation with the sum:

• Finding the Lth and Rth odd-length palindromic numbers
• Modular exponentiation

Each of these should be separate - independently testable - functions; main() then only needs to read input, call the functions and print output.

---

Let's look at the exponentiation first. Putting your code into a function with reasonable names gives

long modexp(int base, int power, int modulus)
{
    long product = 1;
    for (int j = 1;  j <= power;  ++j)
        product = product * base % modulus;
    return product;
}

This is pretty slow, as it has to perform power multiplications. It's better to implement a binary exponentiaton, which scales as the log of the power:

long modexp(int base, int power, int modulus)
{
    long product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = 1L * base * base % modulus;
        power /= 2;
    }
    return product;
}

(Note that this won't handle the full range of int correctly; it's enough for the subset of values we'll encounter in this problem. For a thorough implementation of an unbounded modular exponentiation, have a look at Modular exponentiation without range restriction here on Code Review.)

---

With that first easy win under our belt, let's turn our attention to the palindromes.

We don't need to iterate through all the possible palindromes. The pattern is quite simple: for a given number n, the n th odd-length palindrome is simply n followed by the reverse of n/10.

That's quite easy to compute without iterating:

int odd_palindrome(int n)
{
    int palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

---

We can now create a function to calculate the required function of the sequence of palindromes:

long compute_result(int left, int right)
{
    int sum = 0;
    for (int i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, 1000000007);
}

---

Having tested these functions (not shown here, to keep the answer reasonably short), we can put it all together (using types that are guaranteed large enough to represent the expected range of values), getting something which is more efficient and easier to follow than the posted code:

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef uint_fast32_t u32;
typedef uint_fast64_t u64;

const u32 result_modulus = 1000000007;

static u64 modexp(u64 base, u64 power, u32 modulus)
{
    u64 product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = base * base % modulus;
        power /= 2;
    }
    return product;
}

static u32 odd_palindrome(u32 n)
{
    u32 palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

static u64 compute_result(u32 left, u32 right)
{
    u64 sum = 0;
    for (u32 i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, result_modulus);
}

int main(void)
{
    int ntests;
    if (scanf("%d", &ntests) != 1) {
        return 1;
    }

    while (ntests --> 0) {
        u32 left, right;
        if (scanf("%"SCNuFAST32" %"SCNuFAST32, &left, &right) != 2) {
            return 1;
        }
        printf("%"PRIuFAST64"\n", compute_result(left, right));
    }
}

Answer 2

Brute-force searching is severely inefficient.
Try for a better algorithm by observing the problem carefully:

Algorithm:

Finding a way to easily find the n-th smallest palindrome number begins with a basic question:

How many are there for a given number of digits?

digits	count of palindrome numbers
0	none (or does zero count?)
1	9 (or 10 with zero), 1-digit number
2	9, 1-digit number mirrored
3	90, 2-digit number, mirrored non-duplicated middle
4	90, 2-digit number, mirrored

The odd one out is zero digits (or 1), depending on how zero is treated. Otherwise, the pattern is simple.

Also, if the number doesn't fit (the only possible error), I decided to return zero.

Casting that in code:

unsigned long long nth_palindromic_number(unsigned long long n) {
    const unsigned base = 10;
    unsigned long long m = base - 1;
    for (--n; ; m *= base) {
        if (n < m) {
            n += m / (base - 1);
            m = n / base;
            break;
        }
        n -= m;
        if (n < m) {
            n += m / (base - 1);
            m = n;
            break;
        }
        n -= m;
        if (m * base / base != m)
            return 0;
    }
    for (; m; m /= base) {
        if ((n * base + m % base) / base != n)
            return 0;
        n = n * base + m % base;
    }
    return n;
}

See live on coliru.

Implementation

Regarding your code, I'm missing any use of abstractions, specifically functions, to organize your code.

Also, a severe lack of whitespace reduces readability.

And finally, you don't handle any kind of errors.

Answer 3

Forget about code (until the very end) and just consider how you could generate a sorted list of palindromes (of odd length) "by hand".

The first (1-digit) palindromes are 0, 1, ..., 9 i.e. the palindrome at position n (0 ≤ n < 10) in the list is n. After that come 101, 111, 121, ..., but finding them by hand gets tedious (especially since the list is infinite), so it's time to look for a pattern.

In general, any palindrome consisting or more than 1 digit is of the form a ++ d ++ rev a, where a is a positive number, d is a digit, rev a is the reversal of a and ++ means concatenation. The smallest palindrome larger than a ++ d ++ rev a is:

a ++ (d+1) ++ rev a, if d < 9
(a+1) ++ 0 ++ rev (a+1), if d = 9

Ignoring the reversed part this is just the algorithm for "adding 1". The palindrome at position n (n ≥ 10) in the list is therefore (n div 10) ++ (n mod 10) ++ rev (n div 10), where div is integer division and mod is the remainder-function.

Collecting and cleaning gives the following formula for palindrome Pₙ₊₁ at position n (the "+1" is just there to make P₁ the first and not the second palindrome):

n, if 0 ≤ n < 10
n ++ rev (n div 10), if n ≥ 10

This is where I stopped in my previous answer: according to the title the question is how to compute Pₙ, and the formula above surely is trivial enough be translated into code without much thought.

---

The description, however, poses a different question, i.e. not how to compute Pₙ, but how to compute the product of the terms Pₙ^Pₓ (n < x ≤ k) fast. I decided to retract my answer until I had time to answer that one. Now, let's continue...

For the modular residues (10⁹ + 7) any integer type supporting at least 29 bits suffices (and the size of any Pₙ is even less than that at 23 bits, assuming n ≤ 5000). The product of two 29-bits numbers fits in 58 bits, so as long as you're not tardy in replacing intermediate results by their modular residues a typical 64 bit integer type will do.

Computing a single Pₙ takes O(log(n)) time since rev and ++ are linear in the number of digits and the other operations are usually assumed to be O(1). So computing all of the palindromes involved in the expression takes O((n-k) log k). Modular exponentiation takes logarithmic time (unless implemented naively), so computing the terms Pₙ^Pₓ (n < x ≤ k) takes O(log Pₓ) = O(log x) = O(log k) per term, or O((n-k) log k) in total. Modular multiplication of the k-n terms takes O(k-n). Putting it all together the overall performance is O((n-k) log k). n and k and the hidden constants in O() are small so this is fast.

The implementation is straightforward and doesn't need any optimization hacks. The bottleneck is probably the rev function as I reckon that it's not built in natively. At the cost of more complexity and O(n+k) memory you could get rev down to O(1) amortized, but it's not worth the effort.

---

PS: According to the context description the inputs to the problem are T, L and R which don't occur in the problem statement (!) (I can guess what they mean, just like I can guess what your real question is, but I shouldn't have to).

---

Addendum: I couldn't resist mentioning the following performance tweak:

For 0 ≤ m and 0 ≤ p < 10, P₁₀ₘ₊ₚ = m ++ p ++ rev m (define P₀ = 0 to make this true).

Hence the sum P₁₀ₘ + ... + P₁₀ₘ₊ₚ = (p+1)*P₁₀ₘ + ½×p×(p-1)×10^(number of digits of m)

That means that if n=82 and k=3719 you don't need to explicitly compute and sum 3638 palindromes to determine P₈₂ + … + P₃₇₁₉. Instead it suffices to compute P₈₀, P₉₀, …, P₃₇₁₀, which are just 364 palindromes. The formula above essentially handles the missing bits (extra in case of P₈₀) and they can be computed in one go per computed P₁₀ₘ. The final step is to raise Pₙ to the sum. I expect this makes the overall computation up to 10 times faster than the original computation.