3ms C++ solution


  • 0
    A
    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;
        }
    };
    

Log in to reply
 

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