Problem Name: Palindromic Numbers; Not able to optimise the code

Recently I am solving the problem name Palindromic Numbers, and I am not able to find out the idea that will optimise my code so that it can run under the given time-constraint, as editorial for the problem is also not given and my solution is giving TLE.

Code Link: https://www.codechef.com/viewsolution/26776713

Some of the codes which I have seen optimise on the basis of the following logic.

After iterating the loop till sqrt(n) if there is no base in the range [2,sqrt(n)], then there is a loop as follows:

for(digit = n/(sqrt(n) + 1); digit >= 1; --digit) {
    base = n/digit - 1;
    if((n % digit == 0) && ((n / base) == (n % base)) && (digit < base)) {
         printf("%d\n", base);
         break;
    }
}

I am not able to understand the logic behind the above code? Could anyone help me out?
@alei @anon55659401 @ssjgz @vijju123 @aryanc403

@call_me_hypa Your solution for this problem is being accepted, can you explain me your solution in details especially about the idea which I mentioned in my question description.

Thanks

@anon55659401 As nobody is paying attention to this post, could you look into it and help me out about how can I optimise the solution. I have looked into other people successful submission code and most of them optimised the code by adding the code which I mentioned in the description, but I didn’t understand it well.

Hi,

You should give the forums a search. This answer tells the beautiful theory behind this loop :slight_smile:

3 Likes

Thanks @vijju123 for help :grinning:

How he get the base depend on what arithmetic operation roots division and 21 is not Palindromic number when we flip it it is 12 , how he get the number 10101 base 2 and how could 10 become a base it means any number from the open globe could be base but how to calculate it ???