C++ short solution, only need to compare 5 numbers


  • 3
    Z

    This solution is inspired by @awice , refer to https://discuss.leetcode.com/topic/87220/python-simple-with-explanation

    class Solution {
    public:
        string nearestPalindromic(string n) {
            int l = n.size();
            set<long> candidates;
            // biggest, one more digit, 10...01
            candidates.insert(long(pow(10, l)) + 1);
            // smallest, one less digit, 9...9 or 0
            candidates.insert(long(pow(10, l - 1)) - 1);
            // the closest must be in middle digit +1, 0, -1, then flip left to right
            long prefix = stol(n.substr(0, (l + 1) / 2));
            for ( long i = -1; i <= 1; ++i ) {
                string p = to_string(prefix + i);
                string pp = p + string(p.rbegin() + (l & 1), p.rend());
                candidates.insert(stol(pp));
            }
            long num = stol(n), minDiff = LONG_MAX, diff, minVal;
            candidates.erase(num);
            for ( long val : candidates ) {
                diff = abs(val - num);
                if ( diff < minDiff ) {
                    minDiff = diff;
                    minVal = val;
                } else if ( diff == minDiff ) {
                    minVal = min(minVal, val);
                }
            }
            return to_string(minVal);
        }
    };
    

    Here paste the shortened Python version as well

    class Solution(object):
        def nearestPalindromic(self, n):
            """
            :type n: str
            :rtype: str
            """
            # based on @awice and @o_sharp
            l = len(n)
            # with different digits width, it must be either 10...01 or 9...9
            candidates = set((str(10 ** l + 1), str(10 ** (l - 1) - 1)))
            # the closest must be in middle digit +1, 0, -1, then flip left to right
            prefix = int(n[:(l + 1)/2])
            for i in map(str, (prefix - 1, prefix, prefix + 1)):
                candidates.add(i + [i, i[:-1]][l & 1][::-1])
            candidates.discard(n)
            return min(candidates, key=lambda x: (abs(int(x) - int(n)), int(x)))
    

  • 0
    J

    @zqfan Can you please explain the (l & 1) part?


Log in to reply
 

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