Skip to main content

Find the Closest Palindrome

Problem​

Given a string nn 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.

Examples​

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≤181 \leq n.length \leq 18
  • nn consists of only digits.
  • nn does not have leading zeros.
  • nn is representing an integer in the range [1, 101810^18 - 1].

Approach​

To solve the problem, we need to understand the nature of the allowed moves:

  1. Generate Candidate Palindromes:

    • Generate palindromes by reflecting the first half of the number.

    • Create palindromes by incrementing or decrementing the first half of the number.

    • Consider edge cases such as numbers with all 9′s9's or all 0′s0's.

  2. Calculate Distances:

    • For each candidate palindrome, compute the absolute difference from the original number nn.

  3. Select the Closest Palindrome:

    • Among all candidates, select the one with the smallest absolute difference. In case of ties, choose the smaller number.

Solution for Finding the Closest Palindrome​

The given problem involves To find the nearest palindrome to a given number 'n', the idea is to generate potential palindromic candidates close to 'n' and then determine which one is closest in terms of absolute difference.

Code in Java​

class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        int len = n.length();
        
        // Edge cases for 1, 0, 10, 100, etc.
        long smaller = (long) Math.pow(10, len - 1) - 1;
        long larger = (long) Math.pow(10, len) + 1;
        
        // Middle palindrome by modifying the first half
        long prefix = Long.parseLong(n.substring(0, (len + 1) / 2));
        long candidate1 = createPalindrome(prefix, len % 2 == 0);
        long candidate2 = createPalindrome(prefix - 1, len % 2 == 0);
        long candidate3 = createPalindrome(prefix + 1, len % 2 == 0);
        
        // Collecting all candidates
        long[] candidates = {smaller, larger, candidate1, candidate2, candidate3};
        
        // Finding the nearest palindrome
        long nearest = -1;
        for (long candidate : candidates) {
            if (candidate != num) {
                if (nearest == -1 || Math.abs(candidate - num) < Math.abs(nearest - num) ||
                    (Math.abs(candidate - num) == Math.abs(nearest - num) && candidate < nearest)) {
                    nearest = candidate;
                }
            }
        }
        
        return String.valueOf(nearest);
    }
    
    private long createPalindrome(long prefix, boolean isEvenLength) {
        String strPrefix = String.valueOf(prefix);
        StringBuilder sb = new StringBuilder(strPrefix);
        if (!isEvenLength) {
            sb.setLength(sb.length() - 1);
        }
        return Long.parseLong(strPrefix + sb.reverse().toString());
    }
}

Complexity Analysis​

Time Complexity: O(log(n))O(log(n))​

Reason: Time Complexity is O(log(n))O(log(n)), Comparing a constant number of candidates (5 in this case) involves checking their absolute differences with the original number.

Space Complexity: O(1)O(1)​

Reason: O(1)O(1) additional space, excluding the space required to store the input and output since we only use a fixed number of variables.

References