SPOJ Next Palindrome

Question

I am trying to solve the problem of SPOJ 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 from right to left.

Please take a look at the question here.

Instead of looking for brute force, I'm trying to figure out the next palindrome. But my code still returns TLE (i.e. the time limit has been exceeded), and I'm upset ... Could you give 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

Input may be long. The problem statement says "no more than 1,000,000 digits." So there are probably several test cases with several hundred thousand digits. Splitting such a line in half, reversing one half and adding them takes a little time. But as far as I know, Python string processing is pretty good, so there is only a small contribution to the problem.

What takes a lot of time is converting strings of this length to numbers and huge numbers to strings. For K = 10 ** 200000 + 2 one step str_half = str(int(str_half+string[half]) + 1) took almost a second here. It may be faster on your computer, but SPOJ machines are rather slow, one of these events can push you to this deadline.

So, you need to avoid conversions, work directly with string representations (mutable lists of numbers).

Answer 2

So, based on this problem, let's find out what is the longest palindrome for the case when K.length == 1. This case can be safely ignored, since there is no value greater than K, which is the palindrome K. The same applies to K.length == 2. Therefore, the pseudo-code for the evaluation is as follows:

 if K.length <= 2 pass 

When K.length == 3 values ​​that we need are K [0] and K [2], this gives us boundaries. For example, K == 100. the values ​​we care about are 1 and 0. If K [0] is greater than K [2], we know that we must do K [2] = K [0], and we are done. Another example is K == 200, the first value is greater than 202, which is the first simple, equal. If K [0] == K [2] and K <999, we increase 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 you the general form of the algorithm if you are not ultimately stuck.