Top 10 Programming Languages to Learn in 2019

CodeChef's Solutions

The Next Palindrome’s Solution with Approach – CodeChef

Code Chef Solution

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

Related posts
CodeChef's Solutions

Number of Factors Solution with Approach - CodeChef

CodeChef's Solutions

Flipping Coins Solution with Approach - Codechef

CodeChef's Solutions

Marbles' Solution with Approach - Codechef

CodeChef's Solutions

Closing the Tweets Problem's Solution with Approach - CodeChef

Leave a Reply

Your email address will not be published. Required fields are marked *

Improve Your Python

...with a fresh 🐍 Python Trick 💌
code snippet every couple of days:

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

PyBlog will use the information you provide on this form to be in touch with you and to provide updates and marketing.