# Find the Closest Palindrome number

Difficulty Level Hard
String

## 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.

## Example

123

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;
}```
`111`

### 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;
}
}```
`121`
`111`

### Time complexity

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

String comparison containing wildcards

### 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.

## Implementation For Find the Closest Palindrome number

### C++ code

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mirror(ll ans) {
string a = to_string(ans);
int i = 0;
int j = a.length()-1;
while (i < j) {
a[j--] = a[i++];
}
return stoll(a,nullptr,10);
}
string nearestPalindromic(string n) {
int order =pow(10, n.length()/2);
ll ans = stoll(n,nullptr,10);
ll noChange = mirror(ans);
ll larger = mirror((ans/order)*order + order+1);
ll smaller = mirror((ans/order)*order - 1 );
if ( noChange > ans) {
larger =  min(noChange, larger);
} else if ( noChange < ans) {
smaller = max(noChange, smaller);
}
return to_string( ans - smaller <= larger - ans ? smaller :larger) ;
}
int main()
{
string s="129";
s=nearestPalindromic(s);
cout<<s<<endl;
return 0;
}```
`131`

### Java code

```public String nearestPalindromic(String n) {
int order = (int) Math.pow(10, n.length()/2);
Long ans = Long.valueOf(new String(n));
Long noChange = mirror(ans);
Long larger = mirror((ans/order)*order + order+1);
Long smaller = mirror((ans/order)*order - 1 );
if ( noChange > ans) {
larger = (long) Math.min(noChange, larger);
} else if ( noChange < ans) {
smaller = (long) Math.max(noChange, smaller);
}
return String.valueOf( ans - smaller <= larger - ans ? smaller :larger) ;
}
Long mirror(Long ans) {
char[] a = String.valueOf(ans).toCharArray();
int i = 0;
int j = a.length-1;
while (i < j) {
a[j--] = a[i++];
}
return Long.valueOf(new String(a));
}```
`129`
`131`

### Time complexity

O(len) where len is the length of the string.