# Find next biggest palindrome

I have written a program for the SPOJ PALIN problem:

A positive integer is called a palindrome if its[decimal representation is the same]from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. …

My program does not seem to be fast enough (needs to run between 2s - 9s). One way I have thought of is getting rid of the string based math but when I coded that, it started to fail on specific numbers. Is there a way to optimize this code that I am not seeing?

Code:

from math import ceil

def next_palindrome(n):
digits = list(str(n))
length = len(digits)
mid = length / 2
rev = int("".join(digits[::-1]))

if all(d == "9" for d in digits):
return n + 2
if length == 1:
return n + 1

left = digits[: int(mid)]
digits[ceil(mid) :] = left[::-1]
palindrome = int("".join(digits))

if palindrome > n:
return palindrome

if length % 2 != 0:
mid = int(mid)
if digits[mid] == "9":
# return int("".join(digits)) + (11 * (10 * (mid - 1)))
return int("".join(digits)) + int(f"11{'0' * (mid - 1)}")

digits[mid] = f"{int(digits[mid])+1}"
return "".join(digits)

left_d, right_d = left[-1], digits[ceil(mid) :]
if left_d == "9" and right_d == "9":
mid = int(mid)
# return int("".join(digits)) + (11 * (10 * (mid - 2)))
return int("".join(digits)) + int(f"11{'0' * (mid - 2)}")

left[-1] = f"{int(left_d) + 1}"
return "".join(left + left[::-1])

t = int(input())
for i in range(t):
n = int(input())
print(next_palindrome(n))


Python strings are already effectively lists of characters. There is no need to convert the string into a list of single character strings. This:

    digits = list(str(n))
rev = int("".join(digits[::-1]))


could be written simply as this:

    digits = str(n)
rev = int(digits[::-1])


eliminating the unnecessary join. Similar improvements may be made throughout the code.

The real speed up comes from realizing palindromes can be easily enumerated.

The nth even-length palindrome is str(n) + str(n)[::-1]

The nth odd-length palindrome is str(n) + str(n)[-2::-1]

n can be determined from the first half of the digits of the input number. If the generated palindrome is not large enough, generate the n+1-th.