2 min to read
Largest palindrome product | Project Euler Solution
Largest palindrome product
Problem Statement:
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
You can find the original question here -> Project Euler
Largest palindrome product - Project Euler Solution in Python
def largestPalindrome(bot, top):
z = 0
for i in range(top, bot, -1):
for j in range(top, bot, -1):
if isPalindrome(i*j):
if i * j > z:
z = i * j
return z
def isPalindrome(num):
return str(num) == str(num)[::-1]
print(largestPalindrome(100,999))
Explanation
-
We will use two functions in this solution. First function isPalindrome() will check if the number is palindrome or not. Second function largestPalindrome() will find the largest palindrome product of two 3-digit numbers.
-
In the largestPalindrome() function we will use two for loops to iterate over the range of 999 to 100. We will check if the product of the two numbers is palindrome or not. If it is palindrome then we will check if it is greater than the previous palindrome product or not. If it is greater then we will update the value of z with the new palindrome product.
Complexity Analysis
- Time complexity : O(n^2). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
- Space complexity : O(1). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.
Share Your Solutions for the Largest palindrome product