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.
A more efficient approach is to realize that the closest palindrome to a number n must be structurally similar to n. The closest palindrome will likely have the same number of digits, or one more, or one less. We can generate a small, constant set of candidate palindromes based on this observation and find the best one among them.
Algorithm
- Let
nbe the input string andLbe its length. Convertnto alongnum. - Initialize a list of candidates.
- Add two boundary candidates:
- The largest palindrome with
L-1digits:(long)Math.pow(10, L - 1) - 1. - The smallest palindrome with
L+1digits:(long)Math.pow(10, L) + 1.
- The largest palindrome with
- Generate candidates with the same number of digits:
- Get the prefix string:
prefixStr = n.substring(0, (L + 1) / 2). - Parse
prefixStrto alongprefixVal. - Iterate
pfromprefixVal - 1toprefixVal + 1. - For each
p, construct a full palindrome string of lengthLby mirroring the string ofp. - Add these generated palindromes to the candidates list.
- Get the prefix string:
- Find the best candidate:
- Initialize
minDiff = Long.MAX_VALUEandresult. - Iterate through each
candidatein the list. - Skip the candidate if it's equal to
num. - Calculate
diff = Math.abs(candidate - num). - If
diffis smaller thanminDiff, updateminDiffandresult. - If
diffis equal tominDiff, updateresultto be the smaller of the currentresultand thecandidate.
- Initialize
- Return the final
resultas a string.
Walkthrough
Instead of searching linearly, we can intelligently construct a small set of candidate palindromes that are likely to be the closest. The key insight is that the closest palindrome to an integer n will have a number of digits equal to n, or n-1, or n+1.
This leads to a set of five primary candidates:
- Largest Palindrome with One Fewer Digit: This is always a sequence of nines (e.g., for
n=100, this candidate is99). This can be calculated as10^(L-1) - 1whereLis the length ofn. - Smallest Palindrome with One More Digit: This is always a
1followed byL-1zeros and another1(e.g., forn=99, this is101). This can be calculated as10^L + 1. - Palindromes with the Same Number of Digits: These are the most likely candidates. A palindrome is defined by its first half. We can take the first half of
n(its prefix) and mirror it to form a palindrome. To account for the closest palindrome being slightly smaller or larger, we generate three candidates from the prefix ofn:- One from
prefix - 1. - One from
prefixitself. - One from
prefix + 1.
- One from
For example, if n = "123", the prefix is "12". We generate palindromes from prefixes 11, 12, and 13, which gives us "111", "121", and "131".
After generating this constant set of (at most) five candidates, we iterate through them. For each candidate, we calculate its absolute difference from n. We keep track of the candidate that yields the minimum difference, making sure to handle ties by choosing the smaller value. The original number n itself is excluded from being a valid answer.
import java.util.List;import java.util.ArrayList; class Solution { public String nearestPalindromic(String n) { long num = Long.parseLong(n); int len = n.length(); List<Long> candidates = new ArrayList<>(); // Candidate 1: 99...9 (L-1 digits) candidates.add((long) Math.pow(10, len - 1) - 1); // Candidate 2: 10...01 (L+1 digits) candidates.add((long) Math.pow(10, len) + 1); // Candidates with same number of digits String prefixStr = n.substring(0, (len + 1) / 2); long prefixVal = Long.parseLong(prefixStr); for (long p = prefixVal - 1; p <= prefixVal + 1; p++) { String pStr = String.valueOf(p); StringBuilder suffix = new StringBuilder(pStr).reverse(); String palindromeStr; if (len % 2 != 0) { palindromeStr = pStr + suffix.substring(1); } else { palindromeStr = pStr + suffix.toString(); } candidates.add(Long.parseLong(palindromeStr)); } long minDiff = Long.MAX_VALUE; long result = -1; for (long candidate : candidates) { if (candidate == num) { continue; } long diff = Math.abs(candidate - num); if (diff < minDiff) { minDiff = diff; result = candidate; } else if (diff == minDiff) { result = Math.min(result, candidate); } } return String.valueOf(result); }}Complexity
Time
O(L), where L is the length of `n`. The number of candidates is constant (five). Generating each candidate involves string manipulations that take O(L) time. The final loop to find the best candidate runs a constant number of times.
Space
O(L), where L is the length of `n`. This space is used to store the candidate strings and other temporary strings during construction.
Trade-offs
Pros
Extremely efficient with a constant number of candidates to check, regardless of the input size.
Optimal time complexity for the given constraints.
Correctly handles all edge cases by considering candidates with different numbers of digits.
Cons
The logic is more complex to devise and implement compared to the brute-force approach.
Requires careful handling of edge cases, such as constructing palindromes from prefixes of varying lengths.
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; }}/** * @param {string} n * @return {string} */ function nearestPalindromic ( n ) { const x = BigInt ( n ); let ans = null ; for ( const t of getCandidates ( n )) { if ( ans === null || absDiff ( t , x ) < absDiff ( ans , x ) || ( absDiff ( t , x ) === absDiff ( ans , x ) && t < ans ) ) { ans = t ; } } return ans . toString (); } function getCandidates ( n ) { const length = n . length ; const res = new Set (); res . add ( BigInt ( Math . pow ( 10 , length - 1 ) - 1 )); res . add ( BigInt ( Math . pow ( 10 , length ) + 1 )); const left = BigInt ( n . substring ( 0 , Math . ceil ( length / 2 ))); for ( let i = left - 1 n ; i <= left + 1 n ; i ++ ) { const prefix = i . toString (); const t = prefix + prefix . split ( '' ) . reverse () . slice ( length % 2 ) . join ( '' ); res . add ( BigInt ( t )); } res . delete ( BigInt ( n )); return res ; } function absDiff ( a , b ) { return a > b ? a - b : b - a ; } class Solution {public: string nearestPalindromic(string n) { long x = stol(n); long ans = -1; for (long t : get(n)) if (ans == -1 || abs(t - x) < abs(ans - x) || (abs(t - x) == abs(ans - x) && t < ans)) ans = t; return to_string(ans); } unordered_set<long> get(string &n) { int l = n.size(); unordered_set<long> res; res.insert((long)pow(10, l - 1) - 1); res.insert((long)pow(10, l) + 1); long left = stol(n.substr(0, (l + 1) / 2)); for (long i = left - 1; i <= left + 1; ++i) { string prefix = to_string(i); string t = prefix + string(prefix.rbegin() + (l & 1), prefix.rend()); res.insert(stol(t)); } res.erase(stol(n)); return res; }};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)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.