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?


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) :][0]
    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())

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.