In this Leetcode Largest Palindrome Product problem solution Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

Leetcode Largest Palindrome Product problem solution


Problem solution in Python.

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9
        min_num = 10 ** (n - 1)
        max_num = 10 ** n - 1       
        
        max_pal = 0
        for i in range(max_num, min_num - 1, -2): 
            if i * i < max_pal:
                break
                
            for j in range(max_num, i - 1, -2):
                product = i * j
                if product % 11 != 0 and product >= max_pal:
                    continue
                if str(product) == str(product)[::-1]:
                    max_pal = product

        return max_pal % 1337

Problem solution in Java.

public int largestPalindrome(int n) {
        if (n == 1) return 9;
        int max = (int) Math.pow(10, n) - 1;
        int max_11 = (max / 11)  * 11;
        long product;
        for (int i=max; i > (int) Math.pow(10, n-1); i--){
            product = Long.parseLong(i + new StringBuilder(String.valueOf(i)).reverse().toString());
            for (long j = max_11; j > (int) Math.pow(10, n-1); j-=11) {
                if ((product/j) / (max+1) == 0){ 
                    if (product%j==0) return (int)(product% 1337);
                }
                else break;
            }
        }
        return -1;
    }

Problem solution in C++.

class Solution {
public:
    int largestPalindrome(int n) {
        long max, min, ans = 0, sum;
        max = static_cast<long>(pow(10, n)) - 1;
        min = max/10 + 1;
        sum = 2 * max;
        while (sum/2 * (sum - sum/2) > ans){
            long i = sum/2, j = sum - sum/2;
            while (j <= max && i >= min){
                long num = i * j;
                if (num > ans && isPalindrome(num)){
                    ans = num;
                    break;
                }
                i--;
                j++;
            }
            sum--;
        }
        return ans % 1337;
    }
    bool isPalindrome(long x){
        long y = 0;
        for (long z = x; z != 0; y = 10 * y + z % 10, z /= 10);
        return x == y;
    }
};


Problem solution in C.

long int creatPalindrome(long int num,int n){
    long int p=num*pow(10,n);
    for(int i=0;i<n;i++){
        p=p+(num/(long int)pow(10,n-i-1))*(long int)pow(10,i);
        num=num%(long int)pow(10,n-i-1);
    }
    return p;
}
int largestPalindrome(int n) {
    if(n==1){return 9;}
    long int p=pow(10,n)-1;
    long int q=p;
    long int temp=pow(10,n-1);
    long int ret=0;
    long int ret1=0;
    while(p>=temp){ 
        ret=creatPalindrome(p,n);
        for(int i=q;i>=temp;i--){
            ret1=ret/i;
            if(ret1>=i){break;}
            if(ret1>=temp&&ret%i==0){return ret%1337;}
        }
        p--;
    }
    return NULL;
}