LeetCode 479: Largest Palindrome Product Solution

Master LeetCode problem 479 (Largest Palindrome Product), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

479. Largest Palindrome Product

Hard

Math Enumeration

Problem Explanation

Explanation

To find the largest palindromic integer that can be represented as the product of two n-digits integers, we can start by generating all possible palindromic numbers with 2n digits. Then, we iterate through these palindromic numbers from the largest one downwards, checking if it can be represented as the product of two n-digits integers. If we find such a number, we return it modulo 1337.

The algorithmic steps are as follows:

Generate all palindromic numbers with 2n digits.
Iterate through these palindromic numbers from the largest one downwards.
Check if the number can be represented as the product of two n-digits integers.
If a valid number is found, return it modulo 1337.

Time complexity: O(10^n), where n is the input integer. Space complexity: O(1)

Solution Code

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;

        int upperBound = (int) Math.pow(10, n) - 1;
        int lowerBound = upperBound / 10;

        long maxNumber = (long) upperBound * (long) upperBound;
        int firstHalf = (int) (maxNumber / (long) Math.pow(10, n));

        boolean found = false;
        long palindrome = 0;

        while (!found) {
            palindrome = createPalindrome(firstHalf);
            for (long i = upperBound; i > lowerBound; i--) {
                if (palindrome / i > maxNumber || i * i < palindrome) {
                    break;
                }
                if (palindrome % i == 0) {
                    found = true;
                    break;
                }
            }
            firstHalf--;
        }
        return (int) (palindrome % 1337);
    }

    private long createPalindrome(int num) {
        String str = num + new StringBuilder().append(num).reverse().toString();
        return Long.parseLong(str);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 479 (Largest Palindrome Product)?

This page provides optimized solutions for LeetCode problem 479 (Largest Palindrome Product) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 479 (Largest Palindrome Product)?

The time complexity for LeetCode 479 (Largest Palindrome Product) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 479 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 479 in Java, C++, or Python.

Back to LeetCode Solutions