Last updated on January 18th, 2025 at 03:27 am

Here, we see a Find the Closest Palindrome LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Companies

Yelp

Level of Question

Hard

Find the Closest Palindrome LeetCode Solution

1. Problem Statement

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:
Input: n = “123”
Output: “121”

Example 2:
Input: n = “1”
Output: “0”
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Palindromic Transformation”. This pattern involves generating or modifying numbers/strings to form palindromes and finding the closest palindrome to a given input.

3. Code Implementation in Different Languages

3.1 Find the Closest Palindrome C++

class Solution {
public:
    string nearestPalindromic(string n) {
        if (n.size() == 1) return string(1, n[0] == '0' ? '1' : n[0] - 1);
        long num = stol(n);
        long p1 = static_cast<long>(pow(10, n.size() - 1) - 1l);
        long p2 = static_cast<long>(pow(10, n.size()) + 1l);
        int l = 0, r = n.size() - 1;
        bool notPalin = false;
        while (l < r) {
            if (n[l] != n[r]) notPalin = true;
            n[r--] = n[l++];
        }
        long p3 = notPalin ? stol(n) : 0;

        string temp = n.substr(0, r + 1);  // left half, including the middle if size is odd
        temp = to_string(stol(temp) + 1l);  // add one to the middle digit
        string temp2{temp};
        if (n.size() % 2 == 1) temp2.pop_back();
        reverse(temp2.begin(), temp2.end());
        temp += temp2;
        long p4 = stol(temp);
        temp = n.substr(0, r + 1);
        temp = to_string(stol(temp) - 1l);
        temp2 = temp;
        if (n.size() % 2 == 1) temp2.pop_back();
        reverse(temp2.begin(), temp2.end());
        temp += temp2;
        long p5 = stol(temp);   

        array<long, 5> arr{p1, p2, p3, p4, p5};
        sort(arr.begin(), arr.end(), [&num](const long& n1, const long& n2) {
            auto diff1 = abs(n1 - num), diff2 = abs(n2 - num);
            return diff1 == diff2 ? n1 < n2 : diff1 < diff2;
        });
        return to_string(arr[0]);
    }
};

3.2 Find the Closest Palindrome Java

class Solution {
    public String nearestPalindromic(String n) {
        long N = Long.parseLong(n), S = previous(String.valueOf(N-1).toCharArray()), L = next(String.valueOf(N+1).toCharArray());
        return String.valueOf(L - N < N - S ? L : S);
    }
    private long previous(char[] s) {
        for(int i = 0, n = s.length; i < (n >> 1); i++) {
            while(s[i] != s[n - 1 - i]) {
                decrement(s, n - 1 - i);
                if(s[0] == '0') return Long.parseLong(new String(s));
            }
        }
        return Long.parseLong(new String(s));
    }
    private void decrement(char[] s, int i) {
        while(s[i] == '0') s[i--] = '9';
        s[i]--;
    }
    private long next(char[] s) {
        for(int i = 0, n = s.length; i < (n >> 1); i++) {
            while(s[i] != s[n - 1 - i]) {
                increment(s, n - 1 - i);
            }
        }
        return Long.parseLong(new String(s));
    }
    private void increment(char[] s, int i) {
        while(s[i] == '9') s[i--] = '0';
        s[i]++;
    }
}

3.3 Find the Closest Palindrome JavaScript

var nearestPalindromic = function (n) {
    const bit = BigInt(n);
    const num = [bit - 1n, bit + 1n];
    while (true) {
        const d1 = getDistance(num[0]);
        if (d1 === 0) break;
        num[0] -= BigInt(d1);
    }
    while (true) {
        const d2 = getDistance(num[1]);
        if (d2 === 0) break;
        num[1] += BigInt(d2);
    }
    return bit - num[0] <= num[1] - bit ? String(num[0]) : String(num[1])
};

function getDistance(n) {
    const s = n + '';
    let i = 0;
    let j = s.length - 1;
    while (i < j) {
        if (s[i++] !== s[j--]) return 10 ** (i - 1);
    }
    return 0;
}

3.4 Find the Closest Palindrome Python

class Solution(object):
    def nearestPalindromic(self, n):
        if n == '0':
            return '1'
        if (n == '10') or (n == '11'):
            return '9'
    
        size = len(n)
        if size == 1:
            return str(int(n)-1)

        p = size//2
        m = n[p] if (size%2 == 1) else ''
        s = n[:p] 
        res0 = s + m + s[::-1] 

        sd = str(int(s+m)-1)
        md = ''
        if m!='':
            md = sd[-1]
            sd = sd[:-1]
        if len(sd+md)!=(len(s)+len(m)):
            if m!='':
                sd = sd + md
                md = ''
            else:
                md = '9'
        res1 = sd + md + sd[::-1]
        sp = str(int(s+m)+1)
        mp = ''
        if m!='':
            mp = sp[-1]
            sp = sp[:-1]
        if len(sp+mp)!=(len(s)+len(m)):
            if m!='':
                mp = ''
            else:
                mp = '0'
                sp = sp[:-1]

        res2 = sp + mp + sp[::-1]

        res_list = sorted([int(r) for r in [res0, res1, res2] if r!=n])
        res_diff = [abs(int(r)-int(n)) for r in res_list]
        res = res_list[res_diff.index(min(res_diff))]
        return str(res)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(L)	O(L)
Java	O(L)	O(L)
JavaScript	O(L)	O(L)
Python	O(L)	O(L)

where, L is the length of the input string n.