| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
Hard |
|
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].
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)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;
}
}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;
}
};func nearestPalindromic(n string) string {
l := len(n)
res := []int{int(math.Pow10(l-1)) - 1, int(math.Pow10(l)) + 1}
left, _ := strconv.Atoi(n[:(l+1)/2])
for _, x := range []int{left - 1, left, left + 1} {
y := x
if l&1 == 1 {
y /= 10
}
for ; y > 0; y /= 10 {
x = x*10 + y%10
}
res = append(res, x)
}
ans := -1
x, _ := strconv.Atoi(n)
for _, t := range res {
if t != x {
if ans == -1 || abs(t-x) < abs(ans-x) || abs(t-x) == abs(ans-x) && t < ans {
ans = t
}
}
}
return strconv.Itoa(ans)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}/**
* @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 - 1n; i <= left + 1n; 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;
}