C++, generate palindrome by DFS, then verify


  • 1
    Z

    The idea is to generate possible palindrome number from great to small, which is 2n or 2n-1 digit. Check whether it is product of 2 n-digit number. If so, return the answer. For n = 2-10, it seems that there is always a number of 2n digit matching the requirements.
    I feel the solution to this question is like brute force, but with a bit optimization.

    class Solution {
    public:
        int largestPalindrome(int n) {
            string s(n*2,'0');
            // for case: abccba
            int ans = helper(s, 0, 2*n-1);
            if (ans != -1) return ans;
            s.pop_back();
            // for case: abcba; This is unnecessary for n: 2-10
            return helper(s, 0, 2*n-2);
        }
    private:
        // build palindrome number from great to small by backtracking
        // check whether it is product of 2 n-digit numbers
        int helper(string& s, int l, int r) {
            if (l > r) return check(s);
            for (int i = 9; i >= 0; i--) {
                if (l == 0 && i == 0) continue;
                s[l] = '0'+i;
                s[r] = '0'+i;
                int ans = helper(s, l+1, r-1);
                if (ans != -1) return ans;
            }
            return -1;
        }
        int check(string& s) {
            int n = (s.size()+1)/2;
            long m = 0;
            for (int i = 0; i < s.size(); i++) 
                m = m*10+s[i]-'0';
            // if exsiting, the smaller numbers is in range [left, right] 
            long left = pow(10, n-1), right = sqrt(m);
            for (long i = right; i >= left && m/i < left*10; i--) {
                if (i*(m/i) == m) return m%1337;
            }
            return -1;
        }
    };
    

Log in to reply
 

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