564. Find the Closest Palindrome

Hard
Topics
Companies
Hint

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.

 

Constraints:

    1 <= n.length <= 18
    n consists of only digits.
    n does not have leading zeros.
    n is representing an integer in the range [1, 1018 - 1].


solution:

package org.example;

public class _Find_the_Closest_Palindrome {
    static class Solution {
        public String nearestPalindromic(String numberStr) {
            long number = Long.parseLong(numberStr);
            if (number <= 10) return String.valueOf(number - 1);
            if (number == 11) return "9";

            int length = numberStr.length();
            long leftHalf = Long.parseLong(numberStr.substring(0, (length + 1) / 2));

            long[] palindromeCandidates = new long[5];
            palindromeCandidates[0] = generatePalindromeFromLeft(leftHalf - 1, length % 2 == 0);
            palindromeCandidates[1] = generatePalindromeFromLeft(leftHalf, length % 2 == 0);
            palindromeCandidates[2] = generatePalindromeFromLeft(leftHalf + 1, length % 2 == 0);
            palindromeCandidates[3] = (long)Math.pow(10, length - 1) - 1;
            palindromeCandidates[4] = (long)Math.pow(10, length) + 1;

            long nearestPalindrome = 0;
            long minDifference = Long.MAX_VALUE;

            for (long candidate : palindromeCandidates) {
                if (candidate == number) continue;
                long difference = Math.abs(candidate - number);
                if (difference < minDifference || (difference == minDifference && candidate < nearestPalindrome)) {
                    minDifference = difference;
                    nearestPalindrome = candidate;
                }
            }

            return String.valueOf(nearestPalindrome);
        }

        private long generatePalindromeFromLeft(long leftHalf, boolean isEvenLength) {
            long palindrome = leftHalf;
            if (!isEvenLength) leftHalf /= 10;
            while (leftHalf > 0) {
                palindrome = palindrome * 10 + leftHalf % 10;
                leftHalf /= 10;
            }
            return palindrome;
        }
    }
    public static void main(String[] args) {
        String numberStr = "123";
        Solution s = new Solution();
        System.out.println(s.nearestPalindromic(numberStr));
    }
}