Next Palindrome

Question

I've written a function which, given a number string, returns the next largest palindrome in string form. For example, if the input string is "4738", the output should be "4774". The original problem description is found here. The function seems to be working for all the tests I have thrown at it so far, but the problem is that it is timing out when I submit it at the website above. Which parts are slow, and how can I improve the performance of this function?

# Algorithm: If replacing the right half of the original number with the 
# mirror of the left half results in a bigger number, return that. 
# Otherwise, increment the left half of the number, then replace the 
# right half of the original number with the mirror of the new left half
# and return.
def next_palindrome(n):
 X = len(n)>>1
 Y = X+(len(n)&1)
 first = n[:X][::-1] 
 second = n[Y:] 
 Z = n[:Y]
 if int(first) > int(second): return Z+first
 else: 
 bar = str(int(Z)+1)
 return bar+bar[:X][::-1]

Answer 1

Your indentation is a little odd. In Python, typically you'd never put two statements on the same line... unless you were code golfing, in which case you'd probably put all the statements on one single line and/or use 1-space indents.

def next_palindrome(n):
 X = len(n)>>1
 Y = X+(len(n)&1)
 first = n[:X][::-1] 
 second = n[Y:] 
 Z = n[:Y]
 if int(first) > int(second):
 return Z+first
 else: 
 bar = str(int(Z)+1)
 return bar+bar[:X][::-1]

The biggest time sink here is going to be the line int(first) > int(second), where you're taking two big strings and converting them to integers. That involves a lot of character comparisons and a lot of multiplications by 10... and with the inputs the grader is probably giving you, it'll involve bignum math, which means memory allocation.

You don't actually need to convert the strings to int (or bignum), since you know that first and second are both strings of digits! You can do this instead:

assert Y >= X, "by construction"
assert len(second) >= len(first), "by construction"
if len(first) == len(second) && first > second:
 assert int(first) > int(second), "because ASCII"

---

I also suspect that

first = n[:X][::-1]

is not the most efficient way to reverse the first X characters of n in Python. I would try something like

first = n[X-1::-1]

But getting rid of the ints speeds up your program by a huge factor, so that the above suggestion is completely negligible. I used the following program to benchmark your code:

import timeit
setup = '''
 your code
'''
print timeit.timeit('next_palindrome("1234"*10000)', number=1000, setup=setup)

Using int(first) > int(second): 4.452 seconds.

Using X == Y and first > second: 0.019 seconds.

---

P.S.: Notice that your code ignores leading zeros in both the input and the output. It thinks that the palindrome following 0110 is 22, not 111; and the palindrome following 99 is 101, not 00100. This is probably fine, but you might enjoy thinking about how to "fix" that issue, too.

• b_pcakes: Thanks for the answer. Can you explain how ascii comparison works? Also, what happens in the case when int(first) > int(second) but X < Y? In this case do I have to fall back to checking using int() again?
• Quuxplusone: @SimonZhu: String comparison in Python works by "dictionary order". Digits work just like letters: "1221" < "312" in Python for the same reason that "abba" < "cab". (Yes, even though int("1221") > int("312"))! As for the second part of your question — I'd advise you to get out a pencil and try to find a case where int(first) > int(second) but len(first) < len(second). You'll figure it out on your own. :)