Nearest Pallindrome

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in companies
eBayAppleMicrosoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
131
159
Sample Output 1:
121
161

Explanation:-
For the First Case:-
The palindrome just greater than 131 is 141
The palindrome just smaller than 131 is 121.
Both have the same absolute difference but 121 is smaller than 141 hence 121 is the answer.

For the Second Case:-
161 is the nearest palindrome.
Sample Input 2
2
121
101
Sample Output 2
111
99
Hint

For a given number find a palindrome number just greater and smaller than a given number.

Approaches (1)
Partition

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.
Time Complexity

O(N), where ‘N’ is the length of the given string.

 

There are total ‘N’ iterations in finding palindrome to the given number.

Space Complexity

O(N), where ‘N’ is the length of the given string.

 

We store the digits to find palindrome to the given number.

Code Solution
(100% EXP penalty)
Nearest Pallindrome
Full screen
Console