# c++ solution with brief comments

• 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;
}
}
};
``````

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