Finding the next palindrome code I have been trying recently to develop a code finding the next palindrome from a certain number. For example, if the input is 800, the output should be 808, as 808 being the next palindrome from 800.

Here's my code. It's fully functional, but on my online judge I get a problem with the time of the execution. My method is not optimal. Any advice on this?

def reverseNumber(a):
   degreMax = findDegree(a)
   result = 0
   while a != 0:
      r = a % 10
      a = a // 10
      result = result + r*10**degreMax
      degreMax = degreMax - 1
   return result

def findDegree(a):
   degre = 0
   while a &gt;= 10:
     a = a/10
     degre = degre + 1
   return degre



def isPalindrome(a):
   test = False
   if reverseNumber(a) == a:
      test = True
   return test

def nextPalindrome(a):
   while isPalindrome(a) == False:
      a = a + 1
   return a



nbTest = int(raw_input())
inputs = []

for i in range(0,nbTest):
   a = int(raw_input())
   inputs.append(a)

for i in range(0,len(inputs)):
   print nextPalindrome(inputs[i])
A bit of style

Before anything, let's rewrite/reorganise the code a bit to make it more pythonic but also easier to test.

Python has a style guide called PEP8. Among other things, you do not follow the naming and spacing conventions. You might find interesting to know that there are various tools to check your code (against PEP8 but also for various other things : pep8, pylint, pychecker, pyflakes and even tools to fix style automatically like autopep8.

Also, it is usual (and very useful) to use an if __name__ == '__main__': guard so that you have your definitions (classes, functions, constants, etc) on one hand and your actual program doing something on the other hand.

So far, your "improved" code looks like :

def reverse_number(a):
    degreMax = find_degree(a)
    result = 0
    while a != 0:
        r = a % 10
        a = a // 10
        result = result + r*10**degreMax
        degreMax = degreMax - 1
    return result


def find_degree(a):
    degre = 0
    while a &gt;= 10:
        a = a/10
        degre = degre + 1
    return degre


def is_palindrome(a):
    test = False
    if reverse_number(a) == a:
        test = True
    return test


def next_palindrome(a):
    while not is_palindrome(a):
        a = a + 1
    return a

if __name__ == '__main__':
    nb_test = int(raw_input())
    inputs = []

    for i in range(0, nb_test):
        a = int(raw_input())
        inputs.append(a)
    # inputs = [5, 10, 303, 800]

    for i in range(0, len(inputs)):
        print next_palindrome(inputs[i])


So far, I haven't done anything relevant as far as performances are concerned and you might think I'm wasting your time here. I'm almost done.

More style

So far, I've done cosmetic changes. A few other changes can be performed to make your code more beautiful but also potentially faster (even if it is very subtle).


Python has a divmod function which does exactly what you are trying to do in reverse_number.
You don't need a temporary variable in is_palindrome.
You don't need to provide first argument to range if you start at 0 and step is 1.
You don't need temporary variable a in your main.
In Python 2 (which is the version I am guessing you are using), range creates a list which might be more than what you want. If you just need something to iterate on, xrange is what you need (in most cases this is what you need and it's why it is the behavior for range in Python 3).
It is the convention to name _ a variable whose variable is not used such as i in your code initialising the input list.
Whenever you are using range and len to iterate over a container, you are most probably doing something wrong. Python provides you a way to iterate over something that can hardly be easier : 

for i in inputs:
    print next_palindrome(i)



It's easy/concise/hard to get wrong/fast.


to create a list and fill it, instead of having a boring loop and append, Python has a very expressive way to do it : list comprehension. If you have never read about them, make yourself a favor and just google it. In your case, defining your inputs gets down to this :

    inputs = [int(raw_input()) for _ in xrange(nb_test)]

you can use division assignment /= to write a /= 10 instead of a = a/10. Also (and this is more common), you can use += and -= in various places of your code.
you don't even need to store inputs into an array, you can just compute and print answers as you do over inputs.


At this stage, your code looks like :

def reverse_number(a):
    degreMax = find_degree(a)
    result = 0
    while a != 0:
        a, r = divmod(a, 10)
        result = result + r*10**degreMax
        degreMax -= 1
    return result


def find_degree(a):
    degre = 0
    while a &gt;= 10:
        a /= 10
        degre += 1
    return degre


def is_palindrome(a):
    return reverse_number(a) == a


def next_palindrome(a):
    while not is_palindrome(a):
        a += 1
    return a

if __name__ == '__main__':
    nb_test = int(raw_input())
    inputs = [int(raw_input()) for _ in xrange(nb_test)]
    # inputs = [5, 10, 303, 800]

    for i in inputs:
        print next_palindrome(i)


User interface

A last note before diving into performances. It might be convenient to tell the user what you are asking him. Otherwise, one might think your program is just computing stuff when it is just waiting for input.

nb_test = int(raw_input("Nb tests? "))
inputs = [int(raw_input("Test ? ")) for _ in xrange(nb_test)]


Mesuring performances

In order to improve performance, it is best to be able to measure it while ensuring correctness. This can be achieved through unit tests. Without being bothered with a full unit testing framework, you can just write things like : 

def unit_tests():
    assert next_palindrome(5) == 5
    assert next_palindrome(10) == 11
    assert next_palindrome(80) == 88
    assert next_palindrome(12345678) == 12355321
    assert next_palindrome(1234567890) == 1234664321
    assert next_palindrome(12345678901) == 12345754321
    # assert next_palindrome(123456789012) == ?? too slow..


As your code probably gets too slow for bigger inputs, it's a good option to add a few tests with huge inputs.

Improving performance

Finally!!

You'll probably be disappointed to see that most of the logic you've written can be rewritten using standard functions (this has been said by others):

def is_palindrome(a):
    s = str(a)
    return s == ''.join(reversed(s))


But for a more dramatic improvement, we'll have to look for a totally different algorithm, one that will be very efficient for very huge values. This can be done if you spot a pattern in the different solutions for the different tests we have written.

Let's consider a number with n digits : $$d1,d2,...,dn$$ and let's try to split it in the middle :


if n is odd, we have $$n = 2*k+1$$ and we have 3 parts : $$d1,d2,..,dk$$ in the piece of the left, $$dk+1$$ in the middle, $$dk+2..dn$$ in the piece on the right. Based on the comparison of the left part and of the right part, the next palindrom the left part and its reversed with either dk or dk+1 in the middle.
if n is even, the same logic applies without a middle component.


A few edge cases are to be considered but the following code works on basic cases :

def next_palindrome(a):
    s = str(a)
    n = len(s)
    k, r = divmod(n, 2)
    if r:
        left, mid, right = s[:k], s[k], s[k+1:]
        assert len(left) == len(right) == k
        assert s == left + mid + right
        print(s, left, mid, right)
        mid_n = int(mid)
        if left:
            left_n, right_n, right_n_rev = int(left), int(right), int(right[::-1])
            if left_n &gt; right_n and left_n &gt; right_n_rev:
                return int(left + mid + left[::-1])
            else:
                return int(left + str(mid_n+1) + left[::-1])
        else:
            return mid_n # 1-digit number
    else:
        left, right = s[:k], s[k:]
        assert len(left) == len(right) == k
        assert s == left + right
        print(s, left, right)
        left_n, right_n, right_n_rev = int(left), int(right), int(right[::-1])
        if left_n &gt; right_n and left_n &gt; right_n_rev:
            return int(left + left[::-1])
        else:
            new_left = str(left_n + 1)
            return int(new_left + new_left[::-1])


I've tried (unsucessfully) to give meaningful names to variables.