I want to learn python and i have been using it to solve problems here. Are there any obvious optimizations to the code below. I'm getting TLE. I have tried with huge number of tests containing lengthy numbers and i get output under 1 second. can someone please help me here?
'''
Created on 17-Jul-2011
@author: Naresh
'''
def nextPalindrome1(pal):
length = len(pal)
if (length & 1 == 0):
if length == 0:
return pal
half = length >> 1
if (needsIncrement(pal, half -1, half, length)):
return increment(pal, half -1, half, length)
else:
return pal[0:half-1] + pal[half-1]*2 +(pal[0:half-1])[::-1]
else:
if length == 1:
if (pal == "9"):
return (11)
else:
return int(pal) + 1
half = length >> 1
if (needsIncrement(pal, half, half, length)):
return increment(pal, half, half, length)
else:
return pal[0:half] + pal[half] +(pal[0:half])[::-1]
#
#increments the given number in a efficient way to arrive at the next palindrome
#
def increment(pal, i, j, length):
if (length & 1 == 0):
temp = pal[0:i] + pal[i]*2 +(pal[0:i])[::-1]
else:
temp = pal[0:i] + pal[i] +(pal[0:i])[::-1]
intPal = int(pal)
while (int(temp) <= intPal):
index = i
while(index >= 0):
if (temp[index] != "9"):
break;
index -= 1
if (index == -1):
temp = "1" + ("0" * (j)) + temp[j:length]
else:
temp = temp[0:index] + `int(temp[index]) + 1` + (i - index)*"0" + temp[i+1:length]
length = len(temp)
half = length >> 1
if (length & 1 == 0):
temp = temp[0:half-1] + temp[half-1]*2 +(temp[0:half-1])[::-1]
else:
temp = temp[0:half] + temp[half] +(temp[0:half])[::-1]
return temp
#
#checks if the number needs increment to be a palindrome
#
def needsIncrement(pal, i, j, length):
tempI = i
tempJ = j
while (i >= 0 and j < length):
if (pal[i] < pal[j]):
return True
i-=1
j+=1
while (tempI >= 0 and tempJ < length):
if (pal[tempI] != pal[tempJ]):
return False
tempI -= 1
tempJ +=1
if (tempI == -1 and tempJ == length):
return True
return False
if __name__ == '__main__':
strip = str.strip
import sys
data = sys.stdin.readlines()
for i in range(1, len(data)):
input = strip(data[i])
length = len(input)
j = 0
#
#strip off leading zeroes if present
#
while (j < length):
if (input[j] != '0'):
break
else:
j+=1
str = input[j:length]
if (len(str) == 0 and len(input) > 0):
print "1"
else:
print nextPalindrome1(str)
