C++_AC_by constructing the palindrome number


  • 0
    class Solution {
    public:
    int largestPalindrome(int n) {
        if(n == 1) return 9;
        long max = pow(10, n) - 1;
        long min = max/10;
        for(long i = max; i > min; --i){
            long res = construct(i);
            for(int j = max; j > min; --j){
                if(res / j > max) break;
                if(res % j == 0){
                    return (int)(res % 1337);
                }
            }
        }
        return 0;
    }
    
    long construct(long num){
        long tmp = num;
        long a = 0;
        int n = 0;
        while(tmp){
            a = a * 10 + tmp % 10;
            n++;
            tmp /= 10;
        }
        while(n){
            num = num *10;
            n--;
        }
        return num + a;
    }
    };

  • 0
    M

    In theory, the time complexity of this solution is O((10^n) ** 2). And it apparently leads to a TLE.

    But in practise, you are lucky enough to return early to get the final answer.

    In my opinion, this problem is a nothing more than a trick and make no sense in an real interview.


Log in to reply
 

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