# Project Euler - Problem No.4 - Largest palindrome product

according to the problem:

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.

Here is my code:

def largest_palindrome_product(n:int) -> int:
'''
Returns largest palindrome whose a product of two n digit(base 10) integer
:param n: the number of digits in the numbers we compute the product of
:return: largest palindrome whose a product of two n digit(base 10) integer or -1 if non were found
'''
# Dealing with edge cases
if n == 1:
return 9
elif n < 1:
raise ValueError("Expecting n to be >= 1")

mul_max = -1
upper_boundary = (10**n) - 1
lower_boundary = 10**(n-1)

# Searching for the largest palindrome between the upper boundary and the lower one.
for i in range(upper_boundary, lower_boundary, -1):
for j in range(i, lower_boundary, -1):
str_prod = str(i*j)
if i*j > mul_max and str_prod[::-1] == str_prod:
mul_max = i*j

return mul_max


Here is a small test case for this code:

from ProjectEuler.problem4 import largest_palindrome_product

if __name__ == "__main__":
# largest prime product is of 91*99 -> returns 9009
print(largest_palindrome_product(2))
# Checking edge cases -> returns 9
print(largest_palindrome_product(1))
# largest prime product is of 993*913 -> returns 906609
print(largest_palindrome_product(3))


Let me know your thoughts on this solution :)

• I've rolled back your edit. You cannot incorporate information from any answers (below) into your question, as this invalidates the answers. See what should I do when someone answers my question, especially the "what should I not do" section. – AJNeufeld Aug 1 '19 at 14:57

## Errors

range(start, end) goes from the start value, inclusive, to the end value, exclusive. So

for i in range(upper_boundary, lower_boundary, -1):


will not include lower_boundary in the values which will be tested, so you will be ignoring products where i would be 10 (two digit case) and 100 (three digit case).

Similarly, for j in range(i, lower_boundary, -1) will ignore products where j would be 10 and 100.

The solution is to use range(..., lower_boundary - 1, -1).

## Special Case

Why is n == 1 special cased, to return 9? Why don’t you trust the algorithm to return the correct value? Oh, right, 9*1 wouldn’t be tested, because lower_boundary = 1, and got excluded due to the bug above.

Perhaps you should have examined this special case closer.

## Optimizations

You compute i*j up to 3 times each loop. You should compute it once, and store it in a variable, such as prod.

        prod = i * j
str_prod = str(prod)
if prod > mul_max and str_prod[::-1] == str_prod:
mul_max = prod


You are searching in decreasing ranges for the outer and inner loops. Why? True: You’ll find the target value faster. But you still search all product values where j <= i. Is there any way of determining there won’t be any larger mul_max value, either from the inner loop, or from the outer loop, or both? For instance, if i*j > mul_max is not true, would it be true for any smaller value of j?

Turning a integer into a string is an $$\O(\log n)\$$ operation. Can you skip doing it for every product?

    for j in range(i, lower_boundary - 1, -1):
prod = i * j

if prod <= mul_max:
break

str_prod = str(prod)
if str_prod[::-1] == str_prod:
mul_max = prod


Can something similar be done with the for i in range(...) loop, to speed things up even further?