Largest Palindrome Product

Here is an implementation for the function largestPalindrome, which returns the largest palindromic integer that can be represented as the product of two n-digits integers, modulo 1337.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9

        upper_bound = 10 ** n - 1
        lower_bound = upper_bound // 10

        for a in range(upper_bound, lower_bound, -1):
            candidate = int(str(a) + str(a)[::-1])
            for b in range(upper_bound, lower_bound, -1):
                if candidate // b > upper_bound:
                    break
                if candidate % b == 0:
                    return candidate % 1337

        return -1

Explanation:

1. If n is 1, the largest product will be 9.
2. For other values of n, we construct potential palindromes by taking the number a in the range of n-digit numbers and concatenate it with its reverse.
3. For each candidate palindrome, we check if there exists another n-digit number b such that the candidate is divisible by b. If so, the candidate is a palindrome product of two n-digit numbers.
4. We return the first found palindrome modulo 1337.

The given constraints (1 <= n <= 8) ensure that this code runs efficiently for all input values.

Identifying Problem Isomorphism

“Largest Palindrome Product” can be approximately mapped to “Palindrome Number”.

“Largest Palindrome Product” involves calculating a product and checking if it forms a palindrome. On the other hand, the “Palindrome Number” problem directly checks if a given number is a palindrome.

The reason for approximate mapping is that both problems involve the concept of palindrome numbers. However, it’s not an exact mapping because “Palindrome Number” doesn’t deal with the multiplication aspect present in “Largest Palindrome Product”.

“Palindrome Number” is simpler because it only involves the checking of whether a number is a palindrome or not. The “Largest Palindrome Product” problem is more complex as it involves both multiplication and checking for palindromes.

10 Prerequisite LeetCode Problems

“Largest Palindrome Product” asks for finding the largest palindrome made from the product of two n-digit numbers. Since this problem involves multiplication of large numbers, number theory, and string manipulation to check for palindromes, here are 10 problems as a preparation:

1. 9. Palindrome Number: This problem is useful for understanding how to check if a number is a palindrome.

2. 415. Add Strings: This problem introduces the concept of manipulating large numbers as strings, which will be helpful since the product of two n-digit numbers can be very large.

3. 43. Multiply Strings: This problem is a good practice for the string manipulation of large numbers, specifically for multiplication.

4. 67. Add Binary: While not directly related, the principles of carrying over in addition can be useful when implementing multiplication of large numbers.

5. 125. Valid Palindrome: This problem involves checking if a string is a palindrome, which is similar to checking if the product is a palindrome.

6. 131. Palindrome Partitioning: This problem is a bit more complex but gives more practice with palindromes.

7. 8. String to Integer (atoi): This problem can be useful for understanding how to handle edge cases when converting strings to integers and vice versa.

8. 2. Add Two Numbers: This problem deals with the manipulation of large numbers and can provide useful insights.

9. 204. Count Primes: This problem introduces concepts from number theory which could potentially be useful.

10. 231. Power of Two: Understanding how binary numbers work and how to manipulate them can also be useful for problems involving multiplication of large numbers.

Understanding how to manipulate strings and numbers, check for palindromes, and use number theory principles will help you tackle a wide variety of problems, including the Largest Palindrome Product problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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 Classification

This problem requires finding the largest palindromic product of two numbers. This is a Product Calculation Problem.

Language Agnostic Coding Drills

1. Understanding Problem Statement: Given an integer ’n’, find the largest palindrome that can be made by multiplying two ’n’ digit numbers. If the answer is large, return it modulo 1337.

2. Identifying Sub-problems: In order to solve this problem, we need to identify the sub-problems. These are:

   • Calculating minimum and maximum ’n’ digit numbers.
   • Iterating through all possible combinations of ’n’ digit numbers.
   • Identifying a palindrome number.
   • Keeping track of maximum palindrome found so far.

3. Solving Sub-problems:

   • Calculating minimum and maximum ’n’ digit numbers: We can calculate the minimum ’n’ digit number by raising 10 to the power of ’n - 1’. We calculate the maximum ’n’ digit number by raising 10 to the power of ’n’ and then subtracting 1 from it.
   • Iterating through all possible combinations of ’n’ digit numbers: We iterate through all the numbers from maximum to minimum (both inclusive) and for each iteration we multiply the number with every other number in the same range.
   • Identifying a palindrome number: A number is a palindrome if its reverse is the same as the original. We convert the product of two numbers to string, reverse it and check if it’s equal to the original string.
   • Keeping track of maximum palindrome found so far: We keep a variable that stores the maximum palindrome found so far. If we find a larger palindrome, we update this variable.

4. Combining Solutions: The solution to the main problem is the combination of the solutions to the sub-problems. We initialize ‘max_pal’ to 0. Then, we iterate over the range from ‘max_num’ to ‘min_num’ (both inclusive), in decrementing order. For each number ‘i’ in this range, if its square is less than ‘max_pal’, we break the loop. Inside this loop, we run another loop for each number ‘j’ from ‘max_num’ to ‘i’ (both inclusive), in decrementing order. We calculate the product of ‘i’ and ‘j’ and if this product is divisible by 11 and greater than or equal to ‘max_pal’, we continue. If the product is a palindrome, we update ‘max_pal’. Finally, we return ‘max_pal’ modulo 1337.

The drills should be arranged as follows in increasing level of difficulty:

1. Understanding and Implementing Modulo Operation
2. Understanding and Implementing Power Operation
3. Creating a Loop in Descending Order
4. Multiplying Numbers and Checking for Palindrome
5. Implementing Nested Loops to Try All Combinations
6. Implementing Early Exit from Loop
7. Combining All the Drills to Solve the Problem.

Targeted Drills in Python

1. Understanding and Implementing Modulo Operation

   1 2 3

   a = 15 b = 4 print("The modulo of a and b is", a % b)

2. Understanding and Implementing Power Operation

   1 2 3

   base = 10 exponent = 2 print("The result of base to the power of exponent is", base ** exponent)

3. Creating a Loop in Descending Order

   1 2	for i in range(10, 0, -1): print(i, end=" ")

4. Multiplying Numbers and Checking for Palindrome

   1 2 3 4 5 6 7

   a = 121 b = 1 product = a * b if str(product) == str(product)[::-1]: print(product, "is a palindrome") else: print(product, "is not a palindrome")

5. Implementing Nested Loops to Try All Combinations

   1 2 3

   for i in range(10, 0, -1): for j in range(i, 0, -1): print(i, j)

6. Implementing Early Exit from Loop

   1 2 3 4 5 6

   max_pal = 100 for i in range(10, 0, -1): if i * i < max_pal: print("Exiting loop as the square of", i, "is less than max_pal") break print(i)

7. Combining All the Drills to Solve the Problem

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   def largest_palindrome(n): min_num = 10 ** (n - 1) max_num = 10 ** n - 1 max_pal = 0 for i in range(max_num, min_num - 1, -1): if i * i < max_pal: break for j in range(max_num, i - 1, -1): 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 print(largest_palindrome(2))