3
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – AJNeufeld Aug 1 at 14:57
5
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.