Last Updated: 14 Mar, 2021
Nearest Pallindrome
Moderate
Asked in companies
You have been given a string ‘S' representing a number. Your task is to find the closest palindromic number from this integer represented by 'S'. The closest number is defined as the one for which the absolute difference between the given integer represented by 'S' and the palindrome number is minimum. If more than one number have the same difference then return the smaller integer.
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
Approaches
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.