Formatted question description: https://leetcode.ca/all/564.html

564. Find the Closest Palindrome

Level

Hard

Description

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

Example 1:

Input: “123”

Output: “121”

Note:

  1. The input n is a positive integer represented by string, whose length will not exceed 18.
  2. If there is a tie, return the smaller one as answer.

Solution

For the given integer n, obtain the three closest palindromes, and find the closest palindrome among the three palindromes.

To obtain the three closest palindromes, first obtain the higher half of n. For example, for “123”, the higher half is “12”, and for “1024”, the higher half is “10”. The higher half can be considered as an integer. For the higher half, the higher half plus 1, and the higher half minus 1, generate the palindromes respectively.

One thing that needs to be paid attention to is when the higher half plus 1 has a longer length than the higher half or the higher half minus 1 has a shorter length than the higher half (including the case when the higher half minus 1 is 0). Examples are “990”, “10”, “1024”.

class Solution {
    public String nearestPalindromic(String n) {
        long[] nearestPalindromes = getNearestPalindromes(n);
        long num = Long.parseLong(n);
        long nearest = nearestPalindromes[0];
        long minDifference = Math.abs(num - nearest);
        int length = nearestPalindromes.length;
        for (int i = 1; i < length; i++) {
            long curPalindrome = nearestPalindromes[i];
            long difference = Math.abs(num - curPalindrome);
            if (difference > 0 && difference < minDifference) {
                nearest = curPalindrome;
                minDifference = difference;
            }
        }
        return String.valueOf(nearest);
    }

    public long[] getNearestPalindromes(String n) {
        int length = n.length();
        long min = (long) Math.pow(10, length - 1) - 1;
        long max = (long) Math.pow(10, length) + 1;
        int halfLength = (length + 1) / 2;
        String highHalfStr = n.substring(0, halfLength);
        long highHalf = Long.parseLong(highHalfStr);
        long[] nearestPalindromes = new long[3];
        nearestPalindromes[1] = generatePalindrome(highHalf, length);
        long prevHighHalf = highHalf - 1;
        int prevLength = prevHighHalf == 0 ? 0 : String.valueOf(prevHighHalf).length();
        if (prevLength == halfLength)
            nearestPalindromes[0] = generatePalindrome(prevHighHalf, length);
        else
            nearestPalindromes[0] = min;
        long nextHighHalf = highHalf + 1;
        int nextLength = String.valueOf(nextHighHalf).length();
        if (nextLength == halfLength)
            nearestPalindromes[2] = generatePalindrome(nextHighHalf, length);
        else
            nearestPalindromes[2] = max;
        return nearestPalindromes;
    }

    public long generatePalindrome(long highHalf, int length) {
        String highHalfStr = String.valueOf(highHalf);
        StringBuffer sb = new StringBuffer(highHalfStr);
        for (int i = length / 2 - 1; i >= 0; i--)
            sb.append(highHalfStr.charAt(i));
        return Long.parseLong(sb.toString());
    }
}

All Problems

All Solutions