Find the Closest Palindrome number

Table of Contents

Problem

In Find the Closest Palindrome number problem we have given a number n. Find a number which is a palindrome and the absolute difference between the palindromic number and n is as minimum as possible except zero. If there is more than one number satisfying this condition then print the smaller number.

Find the Closest Palindrome number

Example

Input

123

Output

121

Explanation

A palindromic number smaller than 123 is 121 and their absolute difference is 2. Similarly, a palindromic number greater than 123 is 131 and their absolute difference is 8. So the palindromic number with minimum absolute difference 121.

Brute force approach

As in case if there is more than one number satisfying the minimum absolute difference palindromic condition then we have to select the smaller number. So we first start with decreasing the number and check if it is a palindrome or not. Then we alternatively increase and decrease the given number until we find a palindromic number.

Implementation For Find the Closest Palindrome number

C++ code

// C++ Program to find the closest Palindrome 
// number 
#include <bits/stdc++.h> 
using namespace std; 

// function check Palindrome 
bool isPalindrome(string n) { 
for (int i = 0; i < n.size() / 2; i++) 
  if (n[i] != n[n.size() - 1 - i]) 
  return false; 
return true; 
} 

// convert number into String 
string convertNumIntoString(int num) { 

// base case: 
if (num == 0) 
  return "0"; 

string Snum = ""; 
while (num > 0) { 
  Snum += (num % 10 - '0'); 
  num /= 10; 
} 
return Snum; 
} 

// function return closest Palindrome number 
int closestPlandrome(int num) { 

// case1 : largest palindrome number 
// which is smaller to given number 
int RPNum = num - 1; 

while (!isPalindrome(convertNumIntoString(abs(RPNum)))) 
  RPNum--; 

// Case 2 : smallest palindrome number 
// which is greater than given number 
int SPNum = num + 1; 

while (!isPalindrome(convertNumIntoString(SPNum))) 
  SPNum++; 

// check absolute difference 
if (abs(num - RPNum) > abs(num - SPNum)) 
  return SPNum; 
else
  return RPNum; 
} 

// Driver program to test above function 
int main() { 
int num = 121; 
cout << closestPlandrome(num) << endl; 
return 0; 
}

Java code

public class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        for (long i = 1;; i++) {
            if (isPalindrome(num - i))
                return "" + (num - i);
            if (isPalindrome(num + i))
                return "" + (num + i);
        }
    }
    boolean isPalindrome(long x) {
        long t = x, rev = 0;
        while (t > 0) {
            rev = 10 * rev + t % 10;
            t /= 10;
        }
        return rev == x;
    }
}

Time complexity

O(√n) because in the worst case we may need to traverse 2*√n numbers.

Space complexity

O(1) because we are using constant space.

Efficient Approach

This is the optimized approach. Here we will generate three numbers.

First number

We divide the string into parts and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Second number

We divide the string into parts then add one in the left part of the string and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Third number

We divide the string into parts then subtract one from the left part of the string and takes a mirror of the left part of the string to the right part to make it a palindromic string.

Now we will compare these three numbers and minimum. The number with the minimum absolute difference with the given number is our answer and in case of tie minimum of them is our answer.