Project Euler - Problem No.4 - Largest palindrome product

Question

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 :)

• AJNeufeld: 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.

Answer 1

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?