c++ solution with brief comments


  • 0
    A

    The basic idea is to find the smallest palindromic integer up > n and the largest palindromic integer low < n. This can be done by first adjust n into a palindrome number called pal by copying left half of n into right half in the mirror way. This pal may be smaller, equal or larger than n. Let us assume pal < n. Then pal = low.
    To find up, just consider the left half of the low as an integer and add 1 into it, then copy this new left half into right half in the mirror way. For example, low = 1991, then up = 2002 as 19 + 1 = 20. Also, low = 292, then up = 303 as 29+1 = 30. For the special case if the left half of low is 9, 99, ..., the corresponding value is 11, 101, 1001, ...
    For the case pal > n, the similar idea can apply. If pal = n, we need to find out low and up but using the same approach.

    class Solution {
    public:
        string palindromeStr(const string& s) {
            int i = 0; 
            int j = s.size() - 1;
            string ret = s;
            while (i<=j) {
                ret[j] = ret[i];
                i++;
                j--;
            }
            return ret;
        }
        
        string dec2Palindrome(const string& s) {
            string pal = s;
            int left = (int) (s.size() - 1) / 2; 
            int right = (int) s.size() / 2;
            while (left >= 0) {
                if (pal[left] > '0') {
                    pal[left] = pal[left] - 1;
                    if (left < right) {
                        pal[right] = pal[right] - 1;
                    }
                    break;
                } else {
                    pal[left] = pal[right] = '9';
                    left--;
                    right++;
                }
            }
            if ((pal[0] == '0') && (pal.size() > 1)) {
                pal[right] = '9';
                pal.erase(pal.begin());
            }
            return pal;
        }
        
        string inc2Palindrome(const string& s) {
            string pal = s;
            int left = (int) (s.size() - 1) / 2; 
            int right = (int) s.size() / 2; 
            while (left >= 0) {
                if (pal[left] < '9') {
                    pal[left] = pal[left] + 1;
                    if (left < right) {
                        pal[right] = pal[right] + 1;
                    }
                    break;
                } else {
                    pal[left] = pal[right] = '0';
                    left--;
                    right++;
                }
            }
            if (pal[0] == '0') {
                pal.back() = '1';
                pal.insert(pal.begin(), '1');
            }
            return pal;        
        }
        
        string nearestPalindromic(string n) {
            if (n == "0") {
                return "-1";
            }
            //Find the almost closest palindrome integer
            string pal = palindromeStr(n);
            long low;
            long up;
            long num = stoll(n);
            string lowPal;
            string upPal;
            if (pal == n) {
                //For n is a palindrome number, find the two closest palindrome integer, 
                //one is larger than n and the other is less than n
                lowPal = dec2Palindrome(n);
                upPal = inc2Palindrome(n);            
            }
            //For the other cases, find the corresponding another palindrome integer
            else if (pal < n) {
                lowPal = pal;
                upPal = inc2Palindrome(pal);
            } else {
                upPal = pal;
                lowPal = dec2Palindrome(pal);
            }
            low = stoll(lowPal);
            up = stoll(upPal);
            if (num - low <= up - num) {
                return lowPal;
            } else {
                return upPal;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.