<p>Given a string <code>n</code> representing an integer, return <em>the closest integer (not including itself), which is a palindrome</em>. If there is a tie, return <em><strong>the smaller one</strong></em>.</p>

<p>The closest is defined as the absolute difference minimized between two integers.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = &quot;123&quot;
<strong>Output:</strong> &quot;121&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = &quot;1&quot;
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong> 0 and 2 are the closest palindromes but we return the smallest which is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n.length &lt;= 18</code></li>
	<li><code>n</code> consists of only digits.</li>
	<li><code>n</code> does not have leading zeros.</li>
	<li><code>n</code> is representing an integer in the range <code>[1, 10<sup>18</sup> - 1]</code>.</li>
</ul>

class Solution 
{
public:
    long long halfToPalindrome(long long half, bool isOdd)
    {
        long long res = half;
        if (isOdd) half /= 10;

        while (half)
        {
            res = res * 10 + (half % 10);
            half /= 10;
        }

        return res;
    }

    string nearestPalindromic(string n) 
    {
        vector<long long> candidates;
        int N = n.length();
        long long input = stoll(n);
        long long half = stoll(n.substr(0, (N - 1) / 2 + 1));
        bool isOdd = N % 2 == 1;
        candidates.push_back(halfToPalindrome(half, isOdd));
        candidates.push_back(halfToPalindrome(half + 1, isOdd));
        candidates.push_back(halfToPalindrome(half - 1, isOdd));
        candidates.push_back((long long) pow(10, N - 1) - 1);
        candidates.push_back((long long) pow(10, N) + 1);

        long long diff = LONG_LONG_MAX;
        long long res = 0;
        for (auto cand : candidates)
        {
            if (cand == input) continue;
            if (abs(input - cand) < diff)
            {
                diff = abs(input - cand);
                res = cand;
            }
            else if (abs(input - cand) == diff)
            {
                res = min(res, cand);
            }
        }

        return to_string(res);
    }
};
8300