SPOJ The Next Palindrome

Question

I am trying to solve SPOJ problem 5: find the next largest integer "palindrome" for a given input; that is, an integer that in decimal notation reads the same from left-to-right and right-to-left.

Please have a look of the question here

Instead of using brute force search, I try to calculate the next palindrome. But my code still returns TLE (that is, Time Limit Exceeded) and I am frustrated... Would you mind giving me a hint?

Here is my code in python 3.x

if __name__ == '__main__':
    n = int(input())
    for i in range(n):
        string = input()
        length = len(string)
        ans = ""
        if length %2 == 0 :
            half = length // 2
            str_half = string[0:half]
            ans =  str_half + str_half[::-1]         
            if(ans <= string):
                str_half = str(int(str_half) + 1)
                ans = str_half + (str_half[0:half])[::-1]
            print(ans)
        else:
            half = length // 2
            str_half = string[0:half]
            ans = str_half + string[half] + str_half[::-1]
            if(ans<= string):            
                str_half = str(int(str_half+string[half]) + 1)
                ans = str_half + (str_half[0:half])[::-1]
            print(ans)

Answer 1

The input can be long. The problem statement says "not more than 1000000 digits". So probably there are a couple of test cases with several hundred thousand digits. Splitting such a string in halves, reversing one half and appending them does take a little time. But as far as I know, Python's string handling is pretty good, so that's only a small contribution to the problem.

What is taking a long time is converting strings of such length to numbers and huge numbers to strings. For K = 10 ** 200000 + 2, the step str_half = str(int(str_half+string[half]) + 1) alone took almost a second here. It may be faster on your computer, but SPOJ's machines are quite slow, one such occurrence may push you over the time limit there.

So you have to avoid the conversions, work directly on the string representations (mutable lists of digits).

Answer 2

So based on that problem lets figure out what the longest palindrome is for the case where K.length == 1 . This case can be safely ignored as there is no value larger than K that is a palindrome of K . The same applies to K.length == 2 . Therefore the pseudocode to evaluate this looks as follows:

if K.length <= 2  
     pass  

When K.length == 3 the values we care about are K[0] and K[2] this gives us the boundaries. For example K == 100 . the values we care about are 1 and 0 . If K[0] is larger than K[2] we know that we must make K[2] = K[0] and we are done. Another example is K == 200 the first value larger is 202 which is the first prime that is equal. If K[0] == K[2] and K < 999, we increment K[1] by 1 and we are done. Pseudocode as follows:

if K[0] > K[2]   
      K[2] = K[0]   
if K[0] == K[2] and K < 999  
      K[1]++  

If all values in K are 9 (999,9999, etc) increment K by 2 and end the process. I will leave the general form of the algorithm to you, unless you are ultimately stuck.