Find the Closest Palindrome
HardPrompt
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 <= 18nconsists of only digits.ndoes not have leading zeros.nis representing an integer in the range[1, 1018 - 1].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves converting the input string n to a number and then iteratively checking numbers smaller and larger than n until a palindrome is found in each direction. The one with the smaller absolute difference to n is the answer.
Algorithm
- Convert the input string
nto alongvariablenum. - Find the first palindrome smaller than
num:- Initialize
lower = num - 1. - Loop downwards from
lower, checking if each number is a palindrome. - A number is checked by converting it to a string and verifying if the string is the same forwards and backward.
- Stop when the first smaller palindrome is found.
- Initialize
- Find the first palindrome larger than
num:- Initialize
upper = num + 1. - Loop upwards from
upper, checking if each number is a palindrome. - Stop when the first larger palindrome is found.
- Initialize
- Compare the absolute differences:
|num - lower|and|upper - num|. - If
|num - lower|is less than or equal to|upper - num|, returnlower. Otherwise, returnupper. - Convert the result back to a string.
Walkthrough
The brute-force method is the most straightforward way to conceptualize the problem. The core idea is to search outwards from the given number n in both directions (decreasing and increasing) and stop at the very first palindrome encountered on each side.
- Conversion: The input string
nis first converted into its numerical representation (e.g., alongin Java) to allow for arithmetic operations. - Downward Search: We start a search for the largest palindrome that is smaller than
n. This is done by initializing a variablelowerton - 1and decrementing it in a loop. In each iteration, we check ifloweris a palindrome. The first number that satisfies this condition is our first candidate. - Upward Search: Similarly, we search for the smallest palindrome that is larger than
n. We initializeupperton + 1and increment it until we find a palindrome. - Comparison: After finding both
lowerandupperpalindromes, we determine which one is closer tonby comparing the absolute differencesn - lowerandupper - n. According to the problem statement, if the differences are equal (a tie), we must choose the smaller palindrome, which islower. - Result: The chosen number is then converted back to a string and returned.
To check if a number is a palindrome, a helper function is used. It converts the number to a string and checks if the string reads the same forwards and backward, typically by using a two-pointer technique.
class Solution { public String nearestPalindromic(String n) { long num = Long.parseLong(n); long lower = findLowerPalindrome(num - 1); long upper = findUpperPalindrome(num + 1); long diff1 = num - lower; long diff2 = upper - num; if (diff1 <= diff2) { return String.valueOf(lower); } else { return String.valueOf(upper); } } private long findLowerPalindrome(long limit) { long i = limit; while (true) { if (isPalindrome(String.valueOf(i))) { return i; } i--; } } private long findUpperPalindrome(long limit) { long i = limit; while (true) { if (isPalindrome(String.valueOf(i))) { return i; } i++; } } private boolean isPalindrome(String s) { int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
O(10^(L/2) * L), where L is the length of `n`. The gap between a number and its nearest palindrome can be on the order of `10^(L/2)`. For each number in this gap, we perform a palindrome check which takes O(L) time. This complexity is too high for the given constraints.
Space
O(L), where L is the number of digits in `n`. This space is used to store the string representation of the numbers being checked.
Trade-offs
Pros
Simple to understand and implement.
Logically straightforward.
Cons
Highly inefficient for larger inputs as the distance to the nearest palindrome can be large.
Will likely result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution {public String nearestPalindromic(String n) { long x = Long.parseLong(n); long ans = -1; for (long t : get(n)) { if (ans == -1 || Math.abs(t - x) < Math.abs(ans - x) || (Math.abs(t - x) == Math.abs(ans - x) && t < ans)) { ans = t; } } return Long.toString(ans); }private Set<Long> get(String n) { int l = n.length(); Set<Long> res = new HashSet<>(); res.add((long)Math.pow(10, l - 1) - 1); res.add((long)Math.pow(10, l) + 1); long left = Long.parseLong(n.substring(0, (l + 1) / 2)); for (long i = left - 1; i <= left + 1; ++i) { StringBuilder sb = new StringBuilder(); sb.append(i); sb.append(new StringBuilder(i + "").reverse().substring(l & 1)); res.add(Long.parseLong(sb.toString())); } res.remove(Long.parseLong(n)); return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.