We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Palindrome Product

Difficulty: Hard

Problem Description

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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The largest n-digit integer is 10^n - 1, and the smallest is 10^(n-1).
  • To find the largest palindrome product, we can iterate the possible n-digit integers in reverse order to maximize the product.
  • We need to check if a number is a palindrome by converting it to a string and comparing it to its reverse.

Space and Time Complexity

Time Complexity: O(n^2) - We potentially check all pairs of n-digit numbers. Space Complexity: O(1) - We use a constant amount of space for variables.

Solution

To solve the problem, we use a brute-force approach where we iterate through all pairs of n-digit integers, compute their products, and check if they are palindromic. We keep track of the maximum palindromic product found during the iterations.

Code Solutions

def is_palindrome(x):
    s = str(x)
    return s == s[::-1]

def largest_palindrome(n):
    if n == 1:
        return 9
    upper_limit = 10**n - 1
    lower_limit = 10**(n - 1)
    max_palindrome = 0

    for i in range(upper_limit, lower_limit - 1, -1):
        for j in range(i, lower_limit - 1, -1):
            product = i * j
            if product <= max_palindrome:
                break
            if is_palindrome(product):
                max_palindrome = product

    return max_palindrome % 1337
← Back to All Questions