Given a string n representing an integer, find the closest integer (as a string) that is a palindrome and is not equal to n. If there are multiple such palindromes with the same absolute difference to n, return the smaller one as a string.
n representing an integer (may be very large, so do not assume it fits in a 32-bit integer).n.n itself is a palindrome, do not return n itself.
At first, you might think to check every integer around n (both smaller and larger), and for each, check if it is a palindrome, stopping when you find the closest one. But since n can be huge (up to 18 digits or more), this brute-force approach is not practical.
Instead, we realize that palindromes are structured: they mirror around their center. The closest palindrome to n will likely be one that shares the same prefix as n, or one that is just above or just below n in value. This insight allows us to generate a small set of palindrome candidates by manipulating the first half (or slightly more) of the digits, rather than exhaustively checking all numbers.
n. This includes:
n (using its prefix).n itself if it is a palindrome.n.This approach is efficient because it only considers a handful of candidates, regardless of the number's size.
Example Input: n = "123"
class Solution:
def nearestPalindromic(self, n: str) -> str:
length = len(n)
candidates = set()
# Edge cases: 10..01 and 9..9
candidates.add(str(10 ** length + 1))
candidates.add(str(10 ** (length - 1) - 1))
# Get prefix and generate palindromes by mirroring
prefix = int(n[: (length + 1) // 2])
for i in [-1, 0, 1]:
new_prefix = str(prefix + i)
if length % 2 == 0:
pal = new_prefix + new_prefix[::-1]
else:
pal = new_prefix + new_prefix[:-1][::-1]
candidates.add(pal)
candidates.discard(n)
min_diff = float('inf')
result = None
n_int = int(n)
for cand in candidates:
if cand == n or cand.startswith('-') or cand == '':
continue
cand_int = int(cand)
diff = abs(cand_int - n_int)
if diff < min_diff or (diff == min_diff and cand_int < int(result)):
min_diff = diff
result = cand
return result
class Solution {
public:
string nearestPalindromic(string n) {
int len = n.size();
set<long long> candidates;
// Edge cases
candidates.insert((long long)pow(10, len) + 1);
candidates.insert((long long)pow(10, len - 1) - 1);
long long prefix = stoll(n.substr(0, (len + 1) / 2));
for (int i = -1; i <= 1; ++i) {
string new_prefix = to_string(prefix + i);
string palin = new_prefix;
string rev = new_prefix;
if (len % 2 == 1)
rev.pop_back();
reverse(rev.begin(), rev.end());
palin += rev;
candidates.insert(stoll(palin));
}
candidates.erase(stoll(n));
long long n_num = stoll(n), min_diff = LLONG_MAX, res = -1;
for (auto cand : candidates) {
if (cand == n_num) continue;
long long diff = abs(cand - n_num);
if (diff < min_diff || (diff == min_diff && cand < res)) {
min_diff = diff;
res = cand;
}
}
return to_string(res);
}
};
class Solution {
public String nearestPalindromic(String n) {
int len = n.length();
Set<Long> candidates = new HashSet<>();
candidates.add((long)Math.pow(10, len) + 1);
candidates.add((long)Math.pow(10, len - 1) - 1);
long prefix = Long.parseLong(n.substring(0, (len + 1) / 2));
for (long i = -1; i <= 1; ++i) {
String newPrefix = String.valueOf(prefix + i);
StringBuilder sb = new StringBuilder(newPrefix);
String pal;
if (len % 2 == 0) {
pal = newPrefix + sb.reverse().toString();
} else {
pal = newPrefix + sb.reverse().substring(1);
}
candidates.add(Long.parseLong(pal));
}
candidates.remove(Long.parseLong(n));
long num = Long.parseLong(n), minDiff = Long.MAX_VALUE, res = -1;
for (long cand : candidates) {
if (cand == num) continue;
long diff = Math.abs(cand - num);
if (diff < minDiff || (diff == minDiff && cand < res)) {
minDiff = diff;
res = cand;
}
}
return String.valueOf(res);
}
}
var nearestPalindromic = function(n) {
const len = n.length;
const num = BigInt(n);
let candidates = new Set();
candidates.add((BigInt(10) ** BigInt(len) + 1n).toString());
candidates.add((BigInt(10) ** BigInt(len - 1) - 1n).toString());
let prefix = BigInt(n.slice(0, Math.floor((len + 1) / 2)));
for (let i = -1; i <= 1; ++i) {
let newPrefix = (prefix + BigInt(i)).toString();
let pal;
if (len % 2 === 0) {
pal = newPrefix + newPrefix.split('').reverse().join('');
} else {
pal = newPrefix + newPrefix.slice(0, -1).split('').reverse().join('');
}
candidates.add(pal);
}
candidates.delete(n);
let minDiff = null, result = null;
for (let cand of candidates) {
if (cand === n || cand.startsWith('-') || cand === '') continue;
let candNum = BigInt(cand);
let diff = candNum > num ? candNum - num : num - candNum;
if (minDiff === null || diff < minDiff || (diff === minDiff && candNum < BigInt(result))) {
minDiff = diff;
result = cand;
}
}
return result;
};
n, K can be enormous, making this infeasible.n. We generate a constant number of candidates (at most 5), each with at most 2D digits operations.The optimized solution is efficient even for very large numbers.
By recognizing the structure of palindromes and the constraints of the problem, we avoid brute-force and instead generate only a small set of likely candidates by mirroring the prefix of n. This efficient algorithm ensures we always find the closest palindrome (not equal to n itself), even for very large numbers. The approach is both elegant and practical, leveraging mathematical insight into palindromic numbers.