Short straightforward solution with string conversion


  • 0

    Since the input range n is so limited, I just did a straightforward solution with string to value conversion.

    NOTE: Avoid using C++ function pow(double, double) for floating point issue.

    public:    
        int largestPalindrome(int n) {
            if (n == 1) return 9;
            
            UL half = stoul(string(n,'9')), low = stoul(string(n-1,'9'));
            while (half > low) {
                UL x = getPalindrome(half--);
                if (productN(x, n)) return x%1337;
            }
            return -1;
        }
        
    private:
        typedef unsigned long UL;
        
        // get palindrome number with given first half
        UL getPalindrome(UL half) {
            string s = to_string(half), rev(s.rbegin(),s.rend());
            return stoul(s + rev);
        } 
        
        // check if x is product of two n-digit numbers
        bool productN(UL x, int n) {
            for (UL d = stoul(string(n, '9')); d >= x/d; --d)
                if (x%d == 0 && to_string(x/d).size() == n) return true;
    
            return false;
        }
    

Log in to reply
 

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