# Nearest Pallindrome

Posted: 14 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### Example:

``````Let 'S' is 121. Then the nearest integers are 111 and 131 which are palindrome. Both have the same absolute difference but 111 is smaller. Hence 111 is the answer.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and the only line of each case contains a single string ‘S’ denoting the integer.
``````
##### Output Format:
``````For each test case, return the closest palindrome number from 'S'.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You are not required to print the expected output, it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= T <= 50
0 <= No of digits in ‘S’ <= 18

Time Limit: 1 sec
`````` Approach 1

Explanation: The main idea is for a given number find a palindrome number just greater and smaller than a given number. The one with minimum absolute value is the answer.

Algorithm :

• For a given number find the basic pallindrome by simplifying the first half elements of number to the second half.
• Using this basic pallindrome we will find just larger and just smaller pallindrome number .
• We find the mid and variable ‘i’ pointing to mid.
• For smaller palindrome we will check if S[i] > 0 then we will do S[i]-- and break.
• Else we will do ‘i--’.
• If ‘i’ == 0 and S[i] == 1 then the size of basic palindrome will decrease by one and all digits will be equal to 9.
• Similarly, we will find greater palindrome.
• At last, we will find the closest number(smaller vs greater palindrome) to the given number .
• If both are at the same difference we will return a smaller one else we will return the closest one to the number.