Skip to content

Instantly share code, notes, and snippets.

@drguildo
Created September 10, 2010 21:10
Show Gist options
  • Save drguildo/574386 to your computer and use it in GitHub Desktop.
Save drguildo/574386 to your computer and use it in GitHub Desktop.
def read_input():
import sys
data = []
n = int(input())
for i in range(n):
data.append(input())
return data
def add_one(s):
"""Adds 1 to s where s.isdigit() is true.
>>> add_one("0")
'1'
>>> add_one("11")
'12'
>>> add_one("19")
'20'
>>> add_one("99")
'100'
>>> add_one("909")
'910'
"""
i = len(s) - 1
while (s[i] == "9"):
s = s[:i] + "0" + s[i+1:]
i = i - 1
if (i == -1):
s = "1" + s
else:
s = s[:i] + str(int(s[i]) + 1) + s[i+1:]
return s
def is_palindrome(s):
"""Returns true if s is a palindrome, false otherwise.
>>> is_palindrome("")
True
>>> is_palindrome("x")
True
>>> is_palindrome("xx")
True
>>> is_palindrome("xy")
False
>>> is_palindrome("xyx")
True
>>> is_palindrome("xyyx")
True
"""
if (s == s[::-1]):
return True
else:
return False
def make_palindrome(num):
"""Returns the next highest palindrome of num where num.isdigit() is true.
>>> make_palindrome("0")
'1'
>>> make_palindrome("11")
'22'
>>> make_palindrome("12")
'22'
>>> make_palindrome("120")
'121'
>>> make_palindrome("101")
'111'
>>> make_palindrome("999")
'10001'
>>> make_palindrome("1234")
'1331'
"""
import math
if len(num) == 1: return str(int(num) + 1)
mid = math.ceil(len(num) / 2)
if len(num) % 2 == 0:
a = num[:mid]
br = num[mid:][::-1]
if (br >= a):
a = add_one(a)
ar = a[::-1]
else:
ar = num[:mid][::-1]
return a + ar
else:
a = num[:mid - 1]
ar = num[:mid - 1][::-1]
b = num[mid:]
if (b < ar): return a + num[mid-1] + ar
if (num[mid] < "9"): return a + add_one(num[mid-1]) + ar
a = str(int(a) + 1)
ar = a[::-1]
return a + "0" + ar
if __name__ == "__main__":
nums = read_input()
for num in nums:
print(make_palindrome(num))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment