Last updated on March 2nd, 2025 at 02:07 pm

Here, we see a Largest Palindrome Product LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Companies

Yahoo

Level of Question

Hard

Largest Palindrome Product LeetCode Solution

1. Problem Statement

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.

Example 1:
Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:
Input: n = 1
Output: 9

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Palindrome Construction and Factorization”. The code constructs palindromic numbers by mirroring digits and then checks if the palindrome can be expressed as a product of two n-digit numbers.

3. Code Implementation in Different Languages

3.1 Largest Palindrome Product C++

class Solution {
public:
    int largestPalindrome(int n) {
        if(n==1)
        {
            return 9;
        }
        int hi=pow(10,n)-1;
        int lo=pow(10,n-1);
        int kk=1337;
        for(int i=hi;i>=lo;i--)
        {
            string s=to_string(i);
            string k=s;
            reverse(k.begin(),k.end());
            s+=k;
            long long int ll=stol(s);
            for(int j=hi;j>=sqrtl(ll);j--)
            {
                if(ll%j==0)
                {
                    return ll%kk;
                }
            }            
        }
        return 0;
    }
};

3.2 Largest Palindrome Product Java

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        long upperBound = (long) Math.pow(10, n) - 1;
        long lowerBound = (long) Math.pow(10, n - 1);

        for (long i = upperBound; i >= lowerBound; i--) {
            long palindrome = Long.parseLong(i + new StringBuilder(Long.toString(i)).reverse().toString());
            for (long j = upperBound; j * j >= palindrome; j--) {
                if (palindrome / j > upperBound) {
                    break;
                }
                if (palindrome % j == 0) {
                    return (int) (palindrome % 1337);
                }
            }
        }

        return -1; // This should not be reached
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.largestPalindrome(2));  // Output: 987
        System.out.println(solution.largestPalindrome(1));  // Output: 9        
    }
}

3.3 Largest Palindrome Product JavaScript

var largestPalindrome = function(n) {
    if (n === 1) return 9;
    let hi = BigInt(Math.pow(10, n) - 1);
    let num = hi;
    while(num &gt; 0) {
        num -= 1n;
        const palindrome = BigInt(String(num) + String(num).split('').reverse().join(''));
        for (let i = hi; i &gt;= 2n; i -= 2n) {
            const j = palindrome / i; 
            if (j &gt; hi) break;
            if (palindrome % i === 0n) {
                return String(palindrome % 1337n);
            };
        }
    }
};

3.4 Largest Palindrome Product Python

class Solution(object):
    def largestPalindrome(self, n):
        if n == 1:
            return 9
        upper_bound = 10**n - 1
        lower_bound = 10**(n-1)

        for i in range(upper_bound, lower_bound, -1):
            palindrome = int(str(i) + str(i)[::-1])
            for j in range(upper_bound, int(palindrome**0.5), -1):
                if palindrome // j > upper_bound:
                    break
                if palindrome % j == 0:
                    return palindrome % 1337

solution = Solution()
print(solution.largestPalindrome(2))
print(solution.largestPalindrome(1))

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(10²ⁿ)	O(n)
Java	O(10²ⁿ)	O(n)
JavaScript	O(10²ⁿ)	O(n)
Python	O(10²ⁿ)	O(n)

The time complexity is dominated by the nested loops, which result in O(10²ⁿ).
The space complexity is primarily due to the palindrome construction, which involves string manipulation and requires O(n) space.
The algorithm is computationally expensive for large values of n due to the exponential growth of the search space.