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) -&gt; 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 &lt; 1:
        raise ValueError("Expecting n to be &gt;= 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 &gt; 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 -&gt; returns 9009
    print(largest_palindrome_product(2))
    # Checking edge cases -&gt; returns 9
    print(largest_palindrome_product(1))
    # largest prime product is of 993*913 -&gt; returns 906609
    print(largest_palindrome_product(3))


Let me know your thoughts on this solution :)
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 &gt; 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 &lt;= 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 &gt; 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 &lt;= 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?