CodeChef's Solutions

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.

Related Post

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

Aditya Kumar

Share
Tags: CodeChef Python

Recent Posts

  • Programming

Mastering Print Formatting in Python: A Comprehensive Guide

In Python, the print() function is a fundamental tool for displaying output. While printing simple…

8 months ago
  • Programming

Global Variables in Python: Understanding Usage and Best Practices

Python is a versatile programming language known for its simplicity and flexibility. When working on…

8 months ago
  • Programming

Secure Your Documents: Encrypting PDF Files Using Python

PDF (Portable Document Format) files are commonly used for sharing documents due to their consistent…

8 months ago
  • Programming

Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

PDF (Portable Document Format) files are widely used for document exchange due to their consistent…

8 months ago
  • Programming

Boosting Python Performance with Cython: Optimizing Prime Number Detection

Python is a high-level programming language known for its simplicity and ease of use. However,…

8 months ago
  • Programming

Using OOP, Iterator, Generator, and Closure in Python to implement common design patterns

Object-Oriented Programming (OOP), iterators, generators, and closures are powerful concepts in Python that can be…

8 months ago

This website uses cookies.