Python program to find the next palindrome
Yesterday I wrote a Python program to find the next palindrome to solve this problem from SPOJ. My first accepted solution took four seconds to run. Today I improved the code and now it takes 1.13 seconds. In the rank-list I found people solving this problem with Python program that finishes execution in less than half seconds. Wondering whether I am missing any trick or not using Python properly. :-S
The problem is simple.
As the number can be as large as 1000000 digits, stupid solutions won't finish it's execution in time (thus will get 'Time Limit Exceeded').
I am not going to explain my logic in detail, as I don't want to deprive you of the fun of solving problem. What I basically did was to divide the number into two parts, did some comparison between the corresponding characters (digits) and applied some logics. As soon as I realize that there is some change which made the number larger than it was, I get out of the loop. I don't make any change to the second part of the string, as it's a palindrome, I can generate it from the first part.
If you want to solve the problem, don't forget to test your program using the following numbers:
Here is my code:
The problem is simple.
A positive integer is called a palindrome if its representation in the decimal system is the same when read 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. Numbers are always displayed without leading zeros.
As the number can be as large as 1000000 digits, stupid solutions won't finish it's execution in time (thus will get 'Time Limit Exceeded').
I am not going to explain my logic in detail, as I don't want to deprive you of the fun of solving problem. What I basically did was to divide the number into two parts, did some comparison between the corresponding characters (digits) and applied some logics. As soon as I realize that there is some change which made the number larger than it was, I get out of the loop. I don't make any change to the second part of the string, as it's a palindrome, I can generate it from the first part.
If you want to solve the problem, don't forget to test your program using the following numbers:
0
9
808
2133
199
1999
319887788993
333321
111
1111
999
9999
99999
Here is my code:
def palin(s):
word_len = len(s)
if word_len == 1:
if s == "9":
return "11"
else:
return str(int(s)+1)
if word_len % 2 == 0:
m = ''
else:
m = s[word_len/2]
h1 = (word_len / 2) - 1
h2 = (word_len + 1) / 2
i = h1
j = h2
if m:
while s[i] == s[j]:
i -= 1
j += 1
if i < 0: break
if i < 0 or s[i] < s[j]:
if m == '9':
m = "0"
else:
m = str(int(m) + 1)
return s[:h1+1] + m + s[h1::-1]
while i >= 0:
if s[i] > s[j]:
break
elif s[i] < s[j]:
s = s[:i] + str(int(s[i]) + 1) + "0" * h1
break
elif i > 0:
k = i - 1
l = j + 1
while s[k] == s[l]:
k -= 1
l += 1
if k < 0: break
if k >= 0:
if s[k] < s[l]:
if s[i] == '9':
s = s[:i] + '0' + s[i+1:]
else:
x = str(int(s[i]) + 1)
s = s[:i] + x + s[i+1:]
break
i = k + 1
j = l - 1
else:
if s[i] == '9':
s = s[:i] + '0' + s[i+1:]
else:
x = str(int(s[i]) + 1)
s = s[:i] + x + s[i+1:]
break
else:
if s[i] == '9':
s = s[:i] + '1' + s[i+1:]
m += '0'
break
i -= 1
j += 1
return s[:h1+1] + m + s[h1::-1]
t = int(raw_input())
while t:
t -= 1
s = raw_input()
print palin(s)
Let me know if you can come up with faster and / or more Pythonic solution.
Comments
The other guys who got faster than you may be using some buffering of the results ?
import sys
while True:
line = sys.stdin.readline()
dat = line.strip()
got = False
while not got:
lsiz = len(dat)/2
ksiz = (len(dat)+1)/2
if lsiz == 0:
d = int(dat[0])
print d < 9 and d + 1 or 11
break
for l in xrange(lsiz-1, -1, -1):
r = -1 * (l+1)
if dat[l] == dat[r]:
continue
if dat[l] < dat[r]:
dat = str(int(dat[:ksiz]) + 1)
got = True
print "%s%s" % (dat[:ksiz], dat[(lsiz-1)::-1])
break
if not got:
dat = str(int(dat) + 1)
So, if the user inputs 100 it will return 101 and 99 (the first after and the first before) palindrome.
However, my code is MUCH MUCH smaller than this, why is it so large? I'll try to post it here if I find it.
http://codepad.org/BPyrlREN
******************
def getLowerPalindrome(x):
stringx = str(x)
for i in range(x-1,0,-1):
if str(i) == str(i)[::-1]:
return i
def getHigherPalindrome(x):
stringx = str(x)
for i in range(x+1,9999):
if str(i) == str(i)[::-1]:
return i
if __name__=='__main__':
print getLowerPalindrome(100)
print getHigherPalindrome(100)
*********************
What do you think? Much simpler and easier.
def isPalindrome(s):
sList = list(str(s))
reversedList = sList[:]
reversedList.reverse()
palindrome = True
for i in range(0,len(s)):
a = sList[i]
b = reversedList[i]
if a != b:
palindrome = False
return palindrome
def isPalindrome(s):
sList = list(str(s))
reversedList = sList[:]
reversedList.reverse()
palindrome = True
for i in range(0,len(str(s))):
a = sList[i]
b = reversedList[i]
if a != b:
palindrome = False
return palindrome
def nextPalindrome(n):
found = False
num = n
while found == False:
num += 1
if(isPalindrome(num)):
found = True
return num
myNum = int(input("Enter a number: "))
print("The next palindrome number is: " + str(nextPalindrome(myNum)))
It took you five minutes to code, but it will take forever to execute for larger inputs.
Have you actually read the problem statement? It requires you to find the next palindrome of 1 million digit number, not a number below 1 million.
return len(str(x))%2==1
def above(x):
return x >= rev(x)
def rev(x):
a=str(x)
first_part = a[0:len(a)/2]
if not odd(x):
return int(first_part+first_part[::-1])
else:
return int(first_part+a[len(a)/2]+first_part[::-1])
def bump(x):
a=str(x)
half_point = len(a)/2
if odd(x):
first_half = a[0:half_point+1]
second_half = a[half_point+1:]
else:
first_half = a[0:half_point]
second_half = a[half_point:]
first_int=int(first_half)
first_int+=1
finished = str(first_int)+second_half
return rev(finished)
def nex(x):
if len(str(x))==1:
return 11
if above(x):
return bump(x)
else:
return rev(x)
guess = raw_input('>')
print nex(int(guess))
def next_palindrome(number):
if number == 9:
return 11
if number < 9:
return number+1
temp = str(number)
length = len(temp)
plus = 0
if temp == temp[::-1]:
plus = 1
if length % 2:
beginning = str(int(temp[:(length/2)+1]) + plus)
next = int(beginning + beginning[:-1][::-1])
else:
beginning = str(int(temp[:length/2]) + plus)
next = int(beginning + beginning[::-1])
if next <= number:
return next_palindrome(next)
return next