564

564. Find the Closest Palindrome (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 <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1].

Companies:
Microsoft

Related Topics:
String

Similar Questions:

• Next Palindrome Using Same Digits (Hard)

Solution 1.

Calculate the previous and next palindrome and pick the one with less distance to the original number.

This is too length. Need to read discuss.

// OJ: https://leetcode.com/problems/find-the-closest-palindrome/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    string increment(string s) {
        int carry = 1, i = s.size() - 1;
        for (; i >= 0; --i) {
            carry += s[i] - '0';
            s[i] = carry % 10 + '0';
            carry /= 10;
        }
        if (carry) s.insert(begin(s), carry + '0');
        return s;
    }
    string decrement(string s) {
        int carry = -1, i = s.size() - 1;
        for (; i >= 0; --i) {
            carry += s[i] - '0';
            if (carry < 0) {
                s[i] = (carry + 10) % 10 + '0';
                carry = -1;
            } else {
                s[i] = carry % 10 + '0';
                carry /= 10;
            }
        }
        if (s.size() > 1 && s.front() == '0') s.erase(s.begin());
        return s;
    }
    string nextPalindrome(string &n) {
        auto half = n.substr(0, (n.size() + 1) / 2);
        string reverse(half.rbegin(), half.rend());
        if (lt(n.substr(n.size() / 2), reverse)) return half.substr(0, n.size() - reverse.size()) + reverse;
        auto first = increment(half);
        string second(first.rbegin(), first.rend());
        int len = n.size();
        if (first.size() > half.size()) ++len; // the length of the result will be n.size() + 1
        return first.substr(0, len - first.size()) + second;
    }
    string prevPalindrome(string &n) {
        if (n == "1") return "0";
        auto half = n.substr(0, (n.size() + 1) / 2);
        string reverse(half.rbegin(), half.rend());
        if (lt(reverse, n.substr(n.size() / 2))) return half.substr(0, n.size() - reverse.size()) + reverse;
        auto first = decrement(half);
        if (first.size() < half.size() || first == "0") return string(n.size() - 1, '9');
        string second(first.rbegin(), first.rend());
        return first.substr(0, n.size() - first.size()) + second;
    }
    string subtract(string a, string b) {
        string ans;
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        for (; i >= 0 && j >= 0; --i, --j) {
            carry += a[i] - b[j];
            if (carry >= 0) {
                ans.push_back(carry % 10 + '0');
                carry /= 10;
            } else {
                ans.push_back((carry + 10) % 10 + '0');
                carry = -1;
            }
        }
        while (ans.size() && ans.back() == '0') ans.pop_back();
        reverse(begin(ans), end(ans));
        return ans;
    }
    bool lt(string a, string b) {
        if (a.size() != b.size()) return a.size() < b.size();
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return false;
    }
    bool le(string a, string b) { // returns true if a <= b
        if (a.size() != b.size()) return a.size() < b.size();
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return true;
    }
public:
    string nearestPalindromic(string n) {
        auto a = nextPalindrome(n);
        auto b = prevPalindrome(n);
        return le(subtract(n, b), subtract(a, n)) ? b : a;
    }
};