C++ Using Either String Reverse Or Integer Reverse (670ms)


  • 0
    F

    The palindrome generation function you pick doesn't seem to have a huge impact. Not sure how to shave another 200ms though without extensive hand optimization.

    class Solution {
        size_t palinpow;
    public:
        //returns max and min numbers containing n digits
        std::pair<size_t,size_t> get_digit_bounds(int n)
        {
            return std::make_pair(std::pow(10,n-1),std::pow(10,n)-1);
        }
        std::pair<size_t,size_t> get_palindrome_bounds(int n)
        {
            auto db = get_digit_bounds(n);
            return std::make_pair(db.first*db.first,db.second*db.second);
        }
        
        size_t gen_palindrome(size_t left) //create palindrome given left part
        {
            size_t right = 0;
            //reverse the left part
            for(size_t l=left; l!=0 ; l/=10) right = right*10 +l%10; 
            return left*palinpow+right;
        }
        size_t gen_palindrome_str(size_t left) //generate palindrome using string methods
        {
            auto ls = std::to_string(left);
            auto rs = ls;
            std::reverse(rs.begin(),rs.end());
            return std::stoll(ls+rs);
        }
        
        int largestPalindrome(int n) {
            palinpow = std::pow(10,n);
            //hardcode trivial case
            if (n == 1) return 9;
            auto bounds = get_digit_bounds(n);
            auto palinbounds = get_palindrome_bounds(n);
            for(size_t i=bounds.second ; i>=bounds.first ; --i)
            {
                //skip obviously too big ones
                auto proxy_p = palinpow * i;
                if (proxy_p > palinbounds.second || proxy_p < palinbounds.first) continue;
    
                //generate palindrome
                auto p = gen_palindrome_str(i);
                if (p > palinbounds.second || p < palinbounds.first) continue;
                for(size_t j=bounds.second ; j>= bounds.first; --j)
                {
                    size_t q = p/j;
                    if (q > bounds.second || p > j*j) break; //won't work
                    if (p % j == 0) return p % 1337;
                }
            }
            return 0;
        }
    };
    

Log in to reply
 

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