Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 24

Description

Find the Closest Palindrome

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].

Solution

class Solution {
public:
    string nearestPalindromic(string n) {
        int len = n.length();
        set<long long> ans;
        long long largest = pow(10, len) + 1;
        ans.insert(largest);
        long long smallest = pow(10, len-1) - 1;
        ans.insert(smallest);
        string prefix = string(n.begin(), n.begin()+(len+1)/2);
        long long prefixNum = stoll(prefix);
        for(int i = -1; i <= 1; ++i) {
            long long currentHalf = prefixNum + i;
            string currentHalfString = to_string(currentHalf);
            string currentString = currentHalfString + string(currentHalfString.rbegin()+(len&1), currentHalfString.rend());
            ans.insert(stoll(currentString));
        }
        long long num = stoll(n);
        ans.erase(num);
        long long minDiff = LONG_LONG_MAX, answer = 0;
        for(auto l : ans) {
            if(minDiff > abs(num-l)) {
                minDiff = abs(num-l);
                answer = l;
            }
        }
        return to_string(answer);
    }
};