Nearest Palindrome

XXX. Nearest Palindromic Number

Mathematics

String Manipulation

Problem Statement:

Given a string n representing a positive integer, find the closest integer (not including itself) which is a palindrome. The result should be returned as a string.

If there is a tie, return the smaller integer.

Algorithm:

1. Identify the first half of the input string n, which can be used to generate potential palindrome candidates by mirroring.
2. Generate the following candidates:
   • Palindrome by mirroring the first half.
   • Palindrome by mirroring the first half incremented by 1.
   • Palindrome by mirroring the first half decremented by 1.
   • The largest palindrome smaller than n, such as 999...999.
   • The smallest palindrome larger than n, such as 100...001.
3. Compare all candidates with n and select the one with the smallest absolute difference. If there is a tie, choose the smaller numerical value.

Complexity:

Time Complexity: O(k), where k is the length of the input string n, for generating candidates and comparing them.
Space Complexity: O(1), ignoring the space required for storing the result.

Java Implementation:

class Solution {

    public String nearestPalindromic(String n) {
        int len = n.length();
        int i = len % 2 == 0 ? len / 2 - 1 : len / 2;
        long firstHalf = Long.parseLong(n.substring(0, i + 1));

        // Generate possible palindromic candidates
        List possibilities = new ArrayList<>();
        possibilities.add(halfToPalindrome(firstHalf, len % 2 == 0));
        possibilities.add(halfToPalindrome(firstHalf + 1, len % 2 == 0));
        possibilities.add(halfToPalindrome(firstHalf - 1, len % 2 == 0));
        possibilities.add((long) Math.pow(10, len - 1) - 1); // Smallest n-digit palindrome
        possibilities.add((long) Math.pow(10, len) + 1);     // Largest n-digit palindrome

        // Find the closest palindrome
        long diff = Long.MAX_VALUE, res = 0, num = Long.parseLong(n);
        for (long candidate : possibilities) {
            if (candidate == num) continue; // Skip the number itself
            if (Math.abs(candidate - num) < diff || (Math.abs(candidate - num) == diff && candidate < res)) {
                diff = Math.abs(candidate - num);
                res = candidate;
            }
        }

        return String.valueOf(res);
    }

    private long halfToPalindrome(long left, boolean even) {
        long res = left;
        if (!even) left /= 10; // For odd-length, skip the middle digit
        while (left > 0) {
            res = res * 10 + (left % 10); // Append reversed digits to form palindrome
            left /= 10;
        }
        return res;
    }
}