# 3ms C++ solution

• ``````class Solution {
// modifies the end-half
string makeIntoPalindrome(string n)
{
int digits = n.size();
int mid = digits/2;
int end = digits - 1;

string str;
str.resize(digits);

for (int i = 0; i < mid; ++i)
{
str[i]       = n[i];
str[end - i] = n[i];
}

if ((digits % 2) != 0) // odd
{
str[mid] = n[mid];
}

return str;
}

string nextSmallerPalindrome(string pal)
{
// the input string "pal" should be a palindrome, and the representation of a positive integer

int digits = pal.size();
int mid = digits/2;
int end = digits - 1;

if (digits == 1)
{
--pal[0];
return pal;
}

bool done = false;

int m_left = ((digits % 2) != 0) ? mid : (mid - 1);
int m_right = mid;
while (!done && m_left >= 0)
{
if (pal[m_left] != '0')
{
--pal[m_left];
pal[m_right] = pal[m_left];
done = true;
}
else
{
pal[m_left] = '9';
pal[m_right] = pal[m_left];
--m_left;
++m_right;
}
}

if (pal[0] == '0')
{
pal[end] = '9';
pal = pal.substr(1);
}

return pal;
}

string nextLargerPalindrome(string pal)
{
// the input string "pal" should be a palindrome

int digits = pal.size();
int mid = digits/2;
int end = digits - 1;

bool done = false;

int m_left = ((digits % 2) != 0) ? mid : (mid - 1);
int m_right = mid;
while (!done && m_left >= 0)
{
if (pal[m_left] != '9')
{
++pal[m_left];
pal[m_right] = pal[m_left];
done = true;
}
else
{
pal[m_left] = '0';
pal[m_right] = pal[m_left];
--m_left;
++m_right;
}
}

if (pal[0] == '0')
{
// 100...001
pal.push_back('1');
pal[0] = '1';
}

return pal;
}

public:
string nearestPalindromic(string n)
{
// upto 18 digits. max possible value is 10^19 - 1
// use long long, 10^19 > 2^32 but 10^19 < 2^64

// long long int = std::stoll(str);

// find the first non-zero digit
// incase there are leading zeroes in the string n
size_t index = 0;
while(n[index] == '0')
{
++index;
}

if (index != 0)
{
n = n.substr(index);
}

int digits = n.size();
if (digits == 0) return "1";

long long num = std::stoll(n);

string pal = makeIntoPalindrome(n);

long long smaller, larger;
string smaller_pal, larger_pal;

if (pal == n)
{
smaller_pal = nextSmallerPalindrome(pal);
larger_pal = nextLargerPalindrome(pal);

smaller = std::stoll(smaller_pal);
larger = std::stoll(larger_pal);
}
else
{
smaller = std::stoll(pal);

if (smaller > num)
{
larger_pal = pal;
larger = smaller;

smaller_pal = nextSmallerPalindrome(pal);
smaller = std::stoll(smaller_pal);

}
else
{
smaller_pal = pal;

larger_pal = nextLargerPalindrome(pal);
larger = std::stoll(larger_pal);
}
}

if ((num - smaller) <= (larger - num)) return smaller_pal;
else return larger_pal;
}
};
``````

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