#564

Hard

LeetCode Problem Workspace

Find the Closest Palindrome

Identify the nearest palindrome to a given integer string, handling ties and large numbers efficiently using math and string manipulation.

math string

Problem Statement

You are given a string n representing an integer. Your task is to return the closest integer to n which is a palindrome, excluding n itself. The closest integer is defined as the one minimizing the absolute difference from n. If multiple palindromes are equally close, return the smaller one.

Constraints include 1 <= n.length <= 18, n consists only of digits with no leading zeros, and n represents an integer within [1, 10^18 - 1]. Example: if n = "123", the closest palindrome is "121". For n = "1", the closest palindrome is "0".

Examples

Example 1

Input: n = "123"

Output: "121"

Example details omitted.

Example 2

Input: n = "1"

Output: "0"

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 Approach

Generate Palindrome Candidates

Construct palindromes by mirroring the first half of n, and also consider small adjustments to the mirrored prefix to handle off-by-one cases. Include edge candidates like 10^k + 1 and 10^(k-1) - 1 to cover numeric boundaries.

Compute Differences and Filter

Calculate the absolute difference between each candidate and the original n. Exclude n itself. Keep track of the minimal difference, and if multiple candidates have the same difference, choose the smallest numeric value.

Handle Edge Cases Efficiently

Address single-digit numbers, ties, and very large inputs by explicitly checking boundary palindromes. Avoid brute force across all integers by leveraging string-based palindrome construction.

Complexity Analysis

Metric	Value
Time	O(n \cdot log(m))
Space	O(n)

Time complexity is O(n \cdot log(m)) where n is the length of the string and m is the numeric value used for adjustments. Space complexity is O(n) to store candidate strings and mirrored computations.

What Interviewers Usually Probe

Check if a brute force approach will scale for n up to 10^18.
Consider how string manipulation can generate palindromes instead of numeric iteration.
Ask about tie-breaking rules when multiple palindromes are equally close.

Common Pitfalls or Variants

Common pitfalls

Failing to exclude the input number itself when generating closest palindromes.
Overlooking edge palindromes like 10^k + 1 or 10^(k-1) - 1 which are crucial for very small or large n.
Incorrect tie-breaking logic that returns the larger palindrome instead of the smaller one.

Follow-up variants

Find the closest palindrome larger than the given number.
Find the closest palindrome smaller than the given number.
Count the number of palindromes within a given numeric range.

FAQ

What is the best approach for 'Find the Closest Palindrome' problem?

Use string-based mirroring of the first half with small adjustments, plus boundary checks, to avoid brute force over huge numbers.

Why can't I just iterate over all numbers to find the closest palindrome?

Iterating over all numbers is too slow for n up to 10^18; string manipulation creates only relevant candidates efficiently.

How are ties handled when two palindromes are equally close?

Always choose the smaller numeric palindrome when absolute differences are equal.

Are single-digit numbers treated differently?

Yes, for n = "1" to "9", the closest palindrome can be 0 or n-1, handled explicitly to respect tie-breaking rules.

What edge cases should I watch for in this Math plus String pattern problem?

Watch for numeric boundaries like 10^k + 1, 10^(k-1) - 1, and cases where adjusting the mirrored prefix changes the closest palindrome.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        x = int(n)
        l = len(n)
        res = {10 ** (l - 1) - 1, 10**l + 1}
        left = int(n[: (l + 1) >> 1])
        for i in range(left - 1, left + 2):
            j = i if l % 2 == 0 else i // 10
            while j:
                i = i * 10 + j % 10
                j //= 10
            res.add(i)
        res.discard(x)

        ans = -1
        for t in res:
            if (
                ans == -1
                or abs(t - x) < abs(ans - x)
                or (abs(t - x) == abs(ans - x) and t < ans)
            ):
                ans = t
        return str(ans)

Continue Practicing

#556 next greater element iii #539 minimum time difference #537 complex number multiplication