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 >= 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 >= 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 > right_n and left_n > 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 > right_n and left_n > 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.
