564. Find the Closest Palindrome
Given an integer n, find the closest integer (not including itself), which is a palindrome.
The 'closest' is defined as absolute difference minimized between two integers.
Example 1:
Input: "123" Output: "121"
Note:
- The input n is a positive integer represented by string, whose length will not exceed 18.
- If there is a tie, return the smaller one as answer.
Rust Solution
struct Solution;
impl Solution {
fn nearest_palindromic(n: String) -> String {
let size = n.len();
let half = size / 2;
let value = n.parse::<i64>().unwrap();
let a = 10i64.pow(size as u32);
let b = 10i64.pow(size as u32 - 1);
let mut candidates = vec![a - 1, a + 1, b - 1, b + 1];
if size % 2 == 0 {
let left = n[..half].parse::<i64>().unwrap();
candidates.push(Self::combine(left - 1, false));
candidates.push(Self::combine(left, false));
candidates.push(Self::combine(left + 1, false));
} else {
let left = n[..half + 1].parse::<i64>().unwrap();
candidates.push(Self::combine(left - 1, true));
candidates.push(Self::combine(left, true));
candidates.push(Self::combine(left + 1, true));
}
let mut res = (std::i64::MAX, 0);
for x in candidates {
let diff = (value - x).abs();
if diff == 0 {
continue;
}
if (diff, x) < res {
res = (diff, x);
}
}
(res.1).to_string()
}
fn combine(left: i64, odd: bool) -> i64 {
let l = left.to_string();
l.chars()
.chain(l.chars().rev().skip(if odd { 1 } else { 0 }))
.collect::<String>()
.parse::<i64>()
.unwrap()
}
}
#[test]
fn test() {
let n = "123".to_string();
let res = "121".to_string();
assert_eq!(Solution::nearest_palindromic(n), res);
let n = "8".to_string();
let res = "7".to_string();
assert_eq!(Solution::nearest_palindromic(n), res);
let n = "10".to_string();
let res = "9".to_string();
assert_eq!(Solution::nearest_palindromic(n), res);
let n = "11".to_string();
let res = "9".to_string();
assert_eq!(Solution::nearest_palindromic(n), res);
}
Having problems with this solution? Click here to submit an issue on github.