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

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?