## Find the Closest Palindrome

**Difficulty:** Hard

**Asked in:** Amazon, Microsoft

**Understanding the Problem**

Given an integer k, write a program to find the closest integer (not including itself), which is a palindrome.

**Problem Note:**

- An integer is said to be a palindrome if it remains the same when its digits are reserved.
- 'Closest' means that the absolute difference between two integers should be minimum.
`num`

is a positive integer represented by a string, whose length will not exceed 15 digits.- If two palindromic integers are closest to
`num`

and there is a tie between them, then return the smaller one as output.

**Example 1**

```
Input: "99"
Output: "101"
Explanation: "88" and "101" are two nearest integers which are palindrome. But "101" is the answer because the absolute difference is minimum between "99" and "101".
```

**Solutions**

We will be discussing two approaches for the above problem.

**1. Naive approach**

As we can see that the closest palindrome to a number can be either less than the number or greater than it. For the greater palindrome, the lower limit is number + 1 while for the lower palindrome, the upper limit is number - 1. So, we move further from the number by one and check if it is palindrome or not. This way we get two palindrome numbers - one lower than the number and one greater than the number. Check which one of them is closest (minimum absolute difference) and return it as an answer.

**Pseudo Code**

```
int closestPalindrome(int n)
{
low = n-1
// will decrease the low till low is a palindrome
while(!checkPalindrome(low))
low -= 1
high = n + 1
// will increase the high till high is a palindrome
while(!checkPalindrome(high))
high += 1
// checking difference between both
if ( n - low < high - n)
return low
else
return high
}
```

**Complexity**

Time Complexity:** **O(√N)

Space Complexity:** **O(1)

**2. Efficient Approach**

The property of palindrome is the left side of the palindrome is the mirror image of the right side. So, there is a thinking that if we make any of the sides the same as the other, we can achieve our goal.

**For example, **In the case of “12345”, we mirror “12” to right making it “12321”. Similarly, for 123456, we copy “123” to the right.

Now, the question comes in our mind that which side should we change to make it a palindrome. (**Think!)**

We can copy the left part of the number to the right to get the closest palindrome. (**Why?)**

Let’s dive deeper into why we copy the left to right and not the vice-versa. Suppose the number is "abcxy".

**First way:** Copy the second half to the first half, the new palindrome obtained will be "yxcxy" which has an absolute difference of |10000(a−y)+1000(b−x)| from the original number.

**Second way:** If we copy the first half to the second half of the string, we get "abcba", which has an absolute difference of |10(x−b)+(y−a)|. Trying to change c additionally, in either case, would incur an additional value of at least 100 in the absolute difference.

Thus, we see that it is always better to copy the left to right in such conditions.

There can be cases where you need to check multiple candidate palindromes by changing the middle digits. For Example

`1805170811 `

The first half is 18051. After changing the middle digits, the candidates are 1805005081, 1805115081, and 1805225081. The absolute difference is the minimum for 1805225081. Thus, it is the closest palindrome.

**How to get these candidate palindromes? (Think!)**

We can keep the middle digit same, increment, and decrement the middle digit by 1 and then mirror the left part to get these candidate palindrome numbers.

So, now we know the process to get the closest palindrome, but let's take a look at some corner cases

- If the number is a single-digit number, the closest palindrome is calculated by decrementing 1 from it.
- If the number consists of continuous 9 like 99, 999, 9999 ..., then add 2 to it and get the closest palindrome. But in the case of “9”, return 8 as it is single digit and the closest palindrome to it will be 8 and not 11. For example, 99 has the closest palindrome 101
- If the number is 10, 100, 1000, and so on, subtract 1 from it to get the closest palindrome.

**Pseudo Code**

```
int closestPalindrome(int n)
{
if(n < 10)
return n-1
if(check9(n))
return n + 2
s = str(n) // string representation of n
// Take First Half of string
firstHalf = s.substr(0, s.length() /2)
// if string is of odd length we are storing the odd digit
if (s.size() %2)
odd = s[s.size()/2]
// take second half as reverse of first half
secondHalf = reverse(firstHalf)
// store the palindrome candidates
pal1 = "" // for same middle digit
pal2 = "" // for middle -1 digit
pal3 = "" // for middle + 1 digit
if(s.size()%2)
{
// odd length case
pal1 = firstHalf + odd + secondHalf
if(odd == '0')
{
temp = addCarry(firstHalf, -1)
pal2 = temp + "9" + reverse(temp)
} else
pal2 = firstHalf + str(int(odd) -1) + secondHalf
if(odd == '9')
{
temp = addCarry(firstHalf, 1)
pal3 = temp + '0' + reverse(temp)
} else
pal3 = firstHalf + str(int(odd) + 1) + secondHalf
}
else
{
// even length case
pal1 = firstHalf + secondHalf
smallSize = firstHalf.size() // size of first half
if(firstHalf[smallSize -1] == '0')
temp = addCarry(firstHalf,-1)
else
temp = firstHalf.substr(0,smallSize-1) +
str(int(firstHalf[smallSize-1]) - 1)
pal2 = temp + reverse(temp)
if(firstHalf[smallSize-1] == '9')
temp = addCarry(firstHalf, 1)
else
temp = firstHalf.substr(0, smallSize-1) +
str(int(firstHalf[smallSize-1] - 1))
pal3 = temp + reverse(temp)
}
// return the closest
diff1 = abs(n- pal1)
diff2 = abs(n - pal2)
diff3 = abs(n - pal3)
if(int(pal1) == n)
return diff2 <= diff3 ? int(pal2) : int(pal3)
else if(n > int(pal1))
return diff1 <= diff3 ? int(pal1 : int(pal3)
else
return diff2 <= diff1 ? int(pal2) : int(pal1)
}
// Adding carry to num
string addCarry(string num, int carry)
{
if(carry == -1)
{
itr = num.size() -1
while( itr >= 0 && num[i] == '0')
num[itr--] = '9'
if( itr >= 0)
num[itr] = str(int(num[itr])-1)
}
else
{
for(i = num.size() -1 to 0)
{
temp = int(num[i])
num[i] = str((temp + carry)%10)
carry = (temp + carry) / 10
}
}
return num
}
```

**Complexity**

Time Complexity:** **O(No of Digits)**(Why?)**

Space Complexity:** **O(No of Digits)**(To store the temp variables)**

**Comparison of different solutions**

**Suggested problems to solve**

- Check if a number with even number of digits is palindrome or not.
- Check if a number is a palindrome
- Check if a number is a palindrome in the octal number system
- Find next smallest palindrome

Please comment down below for feedback or if you find a better approach!

**Happy Coding!**