<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:
    bool isPalindromic(string x){ 
        int l=x.length();
        for(int i=0;i<=l/2;i++){
            if(x[i]!=x[l-1-i])
                return false;
        }
        return true;
    }
    // To calculate diff between numbers to find closest among various candidates
    long long diff(string s1, string s2){ 
        // Padding with zeros to do subtraction elegantly
        s1=string(max(s1.length(), s2.length())-s1.length(), '0')+s1;
        s2=string(max(s1.length(), s2.length())-s2.length(), '0')+s2;
        // Reversing to do subtraction from lowest significant digit
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        long long diff=0;
        int max_l=max(s1.length(), s2.length()), i=0;
        while(i<max_l){
            diff+=(long long) (s1[i]-s2[i])*(long long) pow(10,i);
            i++;
        }
        return diff;
    }

    /*
    a helper function to generate a lesser nearby palindrome if s is already palindromic
    Eg:-
    12321 -> first half is 123, we subtract 1 -> 122, then we reflect around 2 -> 12221
    1441 -> first half is 14 -> we subtract 1 -> 13, then we reflect fully -> 1331
        Be careful on how much to reflect based on whether orig string is odd or even long
    */
    string subtractOnefromFirstHalfAndReflect(string s) { 
        int l=s.length();
        string first_half=s.substr(0,ceil(l/2.0));
        int first_half_l=first_half.length();
        if(first_half[first_half_l-1]>'0'){ // If last digit of first half is >0, we can simply subtract
            first_half[first_half_l-1]--;
        } else { // Last digit of first half is 0, so subtraction is not straightforward
            int i=first_half_l-1;
            while(i>=0 && first_half[i]=='0'){ 
                first_half[i]='9'; // Making 9's until we get somewhere to take loan from
                i--;
            }
            first_half[i]--; // Finally taking loan
        }
        if(l%2==0){ // If the orig string was of even length, reflect fully!
            string second_half(first_half.rbegin(), first_half.rend());
            return first_half+second_half;
        } else { // If orig string was of odd length, reflect except last char of first half 
            string first_half_after_trimming=first_half.substr(0,first_half_l-1);// To avoid double copying middle element while reflecting
            string second_half(first_half_after_trimming.rbegin(), first_half_after_trimming.rend());
            return first_half+second_half;
        }
    }

    /*
    a helper function to generate a greater nearby palindrome if s is already palindromic
    Eg:-
    12321 -> first half is 123, we add 1 -> 124, then we reflect around 4 -> 12421
    1441 -> first half is 14 -> we add 1 -> 15, then we reflect fully -> 1551
        Be careful on how much to reflect based on whether orig string is odd or even long
    */
    string addOnefromFirstHalfAndReflect(string s) {
        int l=s.length();
        string first_half=s.substr(0,ceil(l/2.0));
        int first_half_l=first_half.length();
        if(first_half[first_half_l-1]<'9'){ 
            first_half[first_half_l-1]++;
        } else { // Last digit of first half is 9, so addition creates carry
            int i=first_half_l-1;
            while(i>=0 && first_half[i]=='9'){
                first_half[i]='0';
                i--;
            }
            if(i>=0) // If carry doesn't go beyond Most significant digit (MSD)
                first_half[i]++;
            else {// i<0 means carry got forwarded beyond MSD, we need to pad a '1' before 
                first_half="1"+first_half;
                first_half_l++; // length also increased
            }
        }
        if(l%2==0){ // If orig string was of even length
            string second_half(first_half.rbegin(), first_half.rend());
            return first_half+second_half;
        } else { // If orig string was of odd length,
            string first_half_after_trimming= first_half.substr(0,first_half_l-1);
            string second_half(first_half_after_trimming.rbegin(), first_half_after_trimming.rend());
            return first_half+second_half;
        }
    }
    string nearestPalindromic(string n) {
        int i, l=n.length();
        if(l==1) // Corner case for single digit numbers
            return to_string(n[0]-'1');
        // if(n=="11") // Corner case
        //     return "9";
        vector<string> candidates;
        if(!isPalindromic(n)){
            /*  Case 1: If n is not already palindromic, 
            =====================================
            Then we get one candidate by reflecting left part to right. Eg: 1234 -> 1221 OR 54731 -> 54745
            */
            string candidate1=n;
            for(i=0;i<=l/2;i++){
                candidate1[l-1-i]=candidate1[i];
            }
            candidates.push_back(candidate1);
            /*
            That's not it. Consider 1283. Above tactic would yield 1221. But 1331 is more closer to 1283!
            So, don't just reverse first half. Also candidates which are first half +/- 1 and then reverse 
            */
            string candidate2= addOnefromFirstHalfAndReflect(n);
            string candidate3= subtractOnefromFirstHalfAndReflect(n);
            candidates.push_back(candidate2);
            candidates.push_back(candidate3);
            /*
            Special case 1.a)
             What if the number is like 100..00
                Consider 100, we would end up with 101 after reflection. But 99 is also valid and 
                as close to 100 as 101 and is SMALLER! So, 99 is the answer as per tie-breaker.
            */
            string candidate4="";
            for(int k=0;k<l-1;k++){
                candidate4.push_back('9'); 
            }
            candidates.push_back(candidate4);

        } else {
            /* Case 2: If n is already palindromic. 
            ===================================
            Then, we do +/- 1 to first half and then reflect carefully for odd/ even lengths
            12321 -> first half is 123, we subtract 1 -> 122, then we reflect around 2 -> 12221
            12321 -> first half is 123, we add 1 -> 124, then we reflect around 4 -> 12421

            1441 -> first half is 14 -> we subtract 1 -> 13, then we reflect fully -> 1331
            1441 -> first half is 14 -> we add 1 -> 15, then we reflect fully -> 1551
            Special care when you try to subtract when first half ends with 0 as you need loan to subtract 
            and also when you add when the first half ends with 9 because you need to transfer carry
            */
            string candidate1= addOnefromFirstHalfAndReflect(n);
            string candidate2= subtractOnefromFirstHalfAndReflect(n);
            candidates.push_back(candidate1);
            candidates.push_back(candidate2);
            /*
             You might ask why are we adding both candidate1 and candidate2 as you might assume that
             candidate1 and candidate2 are equidistant as we are subtracting 1 or adding one to first half
             and reflecting and that candidate2 being resulted from subtraction would always be optimal as it
             is the smaller one. Like for 174471, both the candidates 175571 and 173371 differ by 1100 and 
             173371 is smaller.
             But this is not always true! Especially whent the first half ends in 0 or 9.
             Consider 11011, candidate1=11111 , candidate2=10901. Here, candidate1 which resulted from addition
             is closer as (11111-11011)= 100 which is less than (11011-10901)=110 
             So, it is better to add both of them to candidates. We anyway check the closeness across all the candidates
            */

            /*
            Special case 2.a) if number was like full of 9's: 99...99
             What if it was 99, candidate1 would be 1001 and candidate2= 88. 
             But neither are optimal as 101 is the nearest palindrome! So, add another candidate for this case
             So, another candidate is 1000...X zeros..001 where x= #digits(n)-1
            */
            string candidate3="1";
            for(int k=0;k<l-1;k++)
                candidate3.push_back('0');
            candidate3.push_back('1');
            candidates.push_back(candidate3);
            /*
            Special case 2.b) If number is like 10001, candidate1 (add 1 to first half and reflect) would be 10101 and 
            candidate2 (subtract 1 from first half and reflect) would be "0990" (but that is not a palindrome!)
            It is not 10001 as well, the optimal answer is 9999. 
            So, for such cases, add 999...  as another candidate
            */
            string candidate4="";
            for(int k=0;k<l-1;k++)
                candidate4.push_back('9');
            candidates.push_back(candidate4);
        }
        // Identifying the optimal across all the candidates from all the cases
        long long min_diff=INT_MAX;
        string optimal_candidate;
        for(string candidate: candidates){
            /*
             For some cases, like for "10001", one candidate via subtraction would yield "0990"
             We should discard this as this is not a palindrome, but the leading zeros is making it 
             look like one
            */
            if(candidate[0]=='0') // Discard candidates generated with leading zeros
                continue;
            long long curr_diff= abs(diff(candidate, n));
            // cout<< "\nCandid: "<<candidate<<" -> diff: "<<curr_diff;
            if(curr_diff <= min_diff){
                if(curr_diff == min_diff){ // If there are multiple candidates equi-distant
                    if(diff(candidate, optimal_candidate)<0){ // Choose the smaller one!
                        min_diff=curr_diff;
                        optimal_candidate=candidate;
                    }
                } else {
                    min_diff=curr_diff;
                    optimal_candidate=candidate;
                }
            }
        }
        return optimal_candidate;
    }
};
10600