Leetcode 564. Find the Closest Palindrome

Problem Explanation:

The problem is about finding the closest palindrome number to a given integer number. The input of the problem is an integer number represented as a string, and it is guaranteed that the string length will not exceed 18. The goal is to compute the nearest palindrome number to the given input and if here is a tie, we should return the smaller number.

To make the problem more clear let's take a look at the example of the problem. Suppose the input number is "123". This number can be read the same way forwards and backwards to be a palindrome. The nearest palindromic numbers for "123" are "121" and "131". As per the problem statement, if there is a tie we have to return the smaller number so here the output is "121".

Solution:

The given solution follows a logical approach to solve the problem. Here are the steps involved in the solution:

• It divides the input number into two halves and reverses the left half and appends it to right. So we will get the candidate palindrome
• If this candidate palindrome less than the input number then it is our closest smaller palindromic number.
• If it is more than input number, then we need to decrement 1 from the left half and reverse it and append it to the right to get the smaller palindromic number
• Similarly, the closest larger palindromic number is found by incrementing 1 to the left half of the number and reversing it and appending to the right.
• Finally, it returns the closest palindromic number to the input number.

Note: Any integer can be read in the same way forwards and backwards it is called a palindromic number, such as "121", "525".

Here is the solution of the problem in several programming languages.

Python

1
2python
3class Solution:
4    def nearestPalindromic(self, n: str) -> str:
5        size = len(n)
6        oddMid = size // 2
7        evenMid = oddMid if size % 2 == 0 else oddMid + 1
8        smaller = int(n[:evenMid] + n[oddMid - 1::-1])
9        larger = int(n[:oddMid] + n[oddMid - 1::-1])
10        for diff in (-1, 1):
11            if smaller < int(n) <= larger:
12                return str(smaller if int(n) - smaller <= larger - int(n) else larger)
13            smaller = larger = int(str(int(n[:evenMid] or '0') + diff) + (n[oddMid - 1::-1] if evenMid else n[oddMid::-1]))

Java

1
2java
3class Solution {
4    public String nearestPalindromic(String n) {
5        long num = Long.parseLong(n);
6        for(long i = 1;; i++) {
7            if(isPalindromic(num - i))
8                return "" + (num - i);
9            if(isPalindromic(num + i))
10                return "" + (num + i);
11        }
12    }
13    
14    public boolean isPalindromic(long x) {
15        long t = x, rev = 0;
16        while(t > 0) {
17            rev = 10 * rev + t % 10;
18            t /= 10;
19        }
20        return rev == x;
21    }
22}

C#

1
2csharp
3public class Solution { 
4        public string NearestPalindromic(string n) {
5                long num = Convert.ToInt64(n), res = long.MinValue, diff = long.MaxValue;
6                for(long i = -1; i<2; i++){
7                    string pre = Convert.ToString(num/long.Parse(Math.Pow(10,n.Length()/2+1).ToString()) + i).Substring(0,n.Length()/2);
8                    string str = pre +(n.Length()%2==0?"" :n.Substring(pre.Length(),1)) + new string(pre.Reverse().ToArray());
9                    long newRes = long.Parse(str);
10                    long newDiff = Math.Abs(num - newRes);
11                    if(num == newRes)
12                        continue;
13                    if(newDiff<diff||(newDiff==diff&&newRes<res)){
14                        res = newRes;
15                        diff = newDiff;
16                    }
17                }
18                return res.ToString();            
19        }
20    }

C++

1
2cpp
3class Solution {
4public:
5    string nearestPalindromic(string n) {
6        long long diff = LONG_MAX, num = stoll(n), res = 0;
7     
8        for(int i = -1; i <= 1; i++){
9            string str = to_string(num/long(pow(10,n.size()/2+1)) + i).substr(0,n.size()/2);
10            str = str+string(str.rbegin()+(n.size()%2)+i,str.rend());
11            long long temp = stoll(str);
12            if(num == temp)
13                continue;
14            long long newDiff = llabs(num - temp);
15            if(newDiff<diff||(newDiff==diff&&temp<res)){
16                res = temp;
17                diff = newDiff;
18            }
19        }
20        return to_string(res);
21    }
22};

JavaScript

1
2javascript
3var nearestPalindromic = function(n) {
4    let len = n.length;
5    let isPalindrome = s => {
6        let len = s.length;
7        for (let i = 0; i < Math.floor(len / 2); ++i)
8            if (s[i] !== s[len - 1 - i]) return false;
9        return true;
10    };
11    for (let i = 1; ; ++i) {
12        if (isPalindrome(String(Number(n) - i))) return String(Number(n) - i);
13        if (isPalindrome(String(Number(n) + i))) return String(Number(n) + i);
14    }
15};

From above methods, we can see that every solution follows a unique algorithm.

The main point when writing out this specific function be it in Python, Java, JavaScript, C# or C++, is to ensure that the level of abstraction gets held up high. This usually happens when your solution abides by the KISS (Keep It Simple, Stupid) principle pretty well.

The general idea is to start off by figuring out what the result will be if the size of the number has to end up changing. In this case, it is straightforward, the answer is always going to be either '10...01', '100...001', '99...99', or '1000...0001' in length.

Once that’s handled, we can simply take care of the remaining problems which are:

1. What if the initial number is a palindrome?
2. The input number can have an even or odd number of digits
3. Sometimes, it is not enough to change the middle digit to find the closest palindrome

Addressing these issues in various languages would involve the following steps:

• Convert the original number into half
• Create the palindrome by reversing the first half and appending it to the original number
• Generate two additional possible solutions by creating a palindrome with the prefix incremented and decremented by one
• Compare and find the closest palindrome to the original number
• Think about the edge cases where you would return 10...01 and 100...001 as solutions

Finally, do not forget to handle some edge cases where the given number is already a palindrome and has zeros as the middle digit(s) to avoid infinite loops.

This algorithm runs with time complexity O(logN), which means it scales well for very large numbers. It is also important to note that although the solutions in different languages use the same algorithmic approach, each language has its own specifics in terms of syntax, built-in function usage, and data conversion.

Overall, this problem provides a good practice not only for the control of strings and numbers, but also for edge case handling, the usage of logic in an algorithm, and ultimately for showcasing your problem-solving skills.