I've been trying to solve this problem for some time, but still no luck . Maybe you folks could help? Here's my code in python:
#!/usr/bin/python
from sys import stdin
def next_palindrome(number):
pos, new_pattern = add_one_with_carry(number, len(number) - 1)
if pos < 0:
number = new_pattern
head = 0
tail = len(number) - 1
carry = 0
while head < tail:
if carry == 1:
pos, number = add_one_with_carry(number, tail)
if pos < head:
head = pos
tail = len(number) - pos - 1
carry = 0
if number[head] != number[tail]:
if number[head] < number[tail]:
carry = 1
number[tail] = number[head]
head += 1
tail -= 1
if carry == 1:
number[tail] = number[head] = number[head] + carry
return number
def add_one_with_carry(pattern, pos):
carry = 1
while carry == 1 and pos >= 0:
num = int(chr(pattern[pos]))
if num == 9:
pattern[pos] = ord('0')
carry = 1
pos -= 1
else:
pattern[pos] = ord(str(num + 1))
carry = 0
else:
if carry == 1 and pos < 0:
new_pattern = bytearray('1', 'ASCII') + pattern
return pos, new_pattern
return pos, pattern
def clean_test_case(line):
pos = 0
if line[pos] != ord('0'):
return line
while pos < len(line) and line[pos] == ord('0'):
pos += 1
if pos == 0 and pos < len(line): return line
else: return line[pos:]
if __name__ == '__main__':
test_cases = None
line = stdin.readline().strip()
if line: test_cases = int(line)
tests = []
while test_cases > 0:
test_cases -= 1
line = stdin.readline().strip()
line = bytearray(line, 'ASCII')
#tests.append(line)
line = clean_test_case(line)
palindrome = next_palindrome(line)
number = palindrome.decode('ASCII').strip()
print(number)
#print("Is pali: " + str(number == number[-1::-1]))
I'm trying the following test cases, and apparently getting the correct answer, according to the simple test I wrote at the end:
19
8 --> 9
0 --> 1
9 --> 11
808 --> 818
2133 --> 2222
8238 --> 8338
55145 --> 55255
999 --> 1001
99 --> 101
99899 --> 99999
9989 --> 9999
99999 --> 100001
0001111 --> 1221
1299976 --> 1300031
5403123 --> 5404045
72939994958 --> 72940004927
129999931 --> 130000031
139999921 --> 140000041
12199121 --> 12200221
Any pointers are greatly appreciated. Thanks!