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:

  1. The input n is a positive integer represented by string, whose length will not exceed 18.
  2. 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.