The Next Palindrome’s Solution with Approach – CodeChef

Problem Statement

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.

---

Input

The first line contains integer t, the number of test cases. Followed by t lines containing integers K.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222 

Solution

Approach

1. Split the word into character list.
2. Check the length and depending on if the list is Even or Odd.
3. Add the first part of the list to the other half in reverse order.
   • 1234333 -> 1234321
   • 5656 -> 5665
4. Join the list and check if it greater than the original word.
   • 1234321 is not greater than 1234333
   • 5665 is greater than 5656. This is the answer.
5. If yes then voila! you go the answer and if not.
6. Increment the middle character and again repeat Step 3 – 5.

Code

import math

def helper(word):
    word_new = ''
    # check is the length of character list is even or odd
    if len(word) % 2 == 1:
        for i in range(len(word)//2 + 1):
            word_new += str(word[i])
        word_new += word_new[:len(word)//2 ][::-1]
    else:
        for i in range(len(word)//2):
            word_new += str(word[i])
        word_new += word_new[::-1]
    return word_new



def solve(word, n):
    string = ''.join([str(x) for x in word])
    z = helper(word)
    if z > string:
        return z
    else:
        # increase the middle character(s) and return the pallindrome
        inc = 1
        for i in range(math.ceil(len(word)/2) - 1,-1,-1):
            word[i] += inc 
            inc = word[i]//10
            word[i] %= 10
        return helper(word)

N = int(input())
for i in range(N):
    word = list(map(int, input()))
    word_len = len(word)

    # for cases like '999','99999'
    if len(set(word))==1 and word[0]==9:
        print('1'+'0'*(word_len-1)+'1')
    else:
        print(solve(word, word_len)) 

Question Link – Link