Largest Palindrome Product - Leetcode Solution

Problem Statement:

Find the largest palindrome made from the product of two n-digit numbers.

Solution:

To solve this problem, we need to generate all possible products of two n-digit numbers and check if they are palindromes. This can be done by iterating over all possible pairs of n-digit numbers and multiplying them. Then, we check if the product is a palindrome and store the largest one.

To implement this algorithm:

1. Define a function to check if a number is a palindrome.
2. Define a function to generate all possible pairs of n-digit numbers, and multiply them.
3. Iterate over all possible pairs of n-digit numbers, and check if their product is a palindrome. Store the largest palindrome.

Here's the implementation of the algorithm in Python:

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

def largest_palindrome_product(n): max_palindrome = -1 for i in range(10**(n-1), 10n): for j in range(10(n-1), 10**n): product = i*j if is_palindrome(product) and product > max_palindrome: max_palindrome = product

return max_palindrome

The is_palindrome function checks if a number is a palindrome. We convert the number to a string, and then reverse it using slicing to check if it is equal to the original string.

The largest_palindrome_product function generates all possible pairs of n-digit numbers, and multiplies them. It then checks if the product is a palindrome and stores the largest palindrome.

We iterate over all possible pairs of n-digit numbers using two nested for loops. We start the loop from 10**(n-1) (which is the smallest n-digit number) and end at 10**n (which is the largest n-digit number).

We multiply the two numbers and store the product in the product variable. We then check if the product is a palindrome using the is_palindrome function. If the product is a palindrome and greater than the current maximum palindrome, we update the max_palindrome variable.

Finally, we return the largest palindrome found.

Example:

n = 3 print(largest_palindrome_product(n))

Output: 906609

In this example, we're looking for the largest palindrome made from the product of two 3-digit numbers. The largest palindrome product found is 906609, which is the product of 993 and 913.

Time Complexity:

The time complexity of this algorithm is O(n^2 * log(m)), where n is the number of digits, and m is the largest product. This is because we iterate over all possible pairs of n-digit numbers, which takes O(n^2) time. The multiplication operation takes O(log(m)) time, where m is the largest product. Checking if the product is a palindrome takes O(n) time.

Space Complexity:

The space complexity of this algorithm is O(1), as we only store a few variables.

1