2
\$\begingroup\$

I am given a task to write a program to find the largest palindrome made from the product of two 3-digit numbers. How can I improve this code?

def check_palindrome(s):
     """Checks whether the given string is palindrome"""

     if s == s[::-1]:
        return True

product_pal = []
for i in range (999,900,-1):
    for j in range (999,900,-1):
        product = i * j
        if check_palindrome(str(product)):
            product_pal.append(product)
            print"i =" , i , "j = ",j, "for", product
print max(product_pal)
\$\endgroup\$
  • \$\begingroup\$ You can keep track of just the current maximum instead of keeping a list of products. \$\endgroup\$ – RobAu Jan 17 '18 at 14:26
  • \$\begingroup\$ You should in general wait a bit before accepting an answer. Some of us live all over the world, so in general in the SE network it is customary to wait at least 24h before accepting an answer. Once a question has an accepted answer, it usually gets less additional answers. You can always un-accept my answer and at a later time decide that it is what you were looking for and accept it again. Or somebody else's. \$\endgroup\$ – Graipher Jan 17 '18 at 16:44
  • \$\begingroup\$ Note that you can break your inner loop after the first palindrome for a given (i, j) pair - you are counting towards lower numbers, and any subsequent palindrome of the form i * (j - m) will be lower than your current i * j. Likewise, if your first discovered palindrome is less than the current max palindrome, break because it won't get bigger. \$\endgroup\$ – Austin Hastings Jan 17 '18 at 23:07
1
\$\begingroup\$

In your check_palindrome function you can directly return the result of the comparison:

def check_palindrome(s):
     """Checks whether the given string is palindrome"""
     return s == s[::-1]

As @RobAu said in the comments, you should keep only the current maximum product, instead of building a (potentially very large) list of all products.

You can also reduce the number of products you need to check by realizing that if you checked 999*998, you don't need to check 998*999. This can be achieved by letting the inner loop start at i.

max_product = 0
for i in range(999, 900, -1):
    for j in range(i, 900, -1):
        product = i * j
        if check_palindrome(str(product)):
            max_product = max(max_product, product)
            print "i =", i, "j = ", j, "for", product
print max_product

Note that Python has an official style-guide, PEP8, which recommends using whitespace to separate operators and after commas in lists (including argument lists).

As a final step, I would make this a function that returns its result, instead of printing it:

def get_max_three_digit_product():
    max_product = 0
    for i in range(999, 900, -1):
        for j in range(i, 900, -1):
            product = i * j
            if check_palindrome(str(product)):
                max_product = max(max_product, product)
    return max_product

This makes the code more re-usable, in case you ever need it again. You can execute it under a if __name__ == "__main__": guard, which allows you to import this function from another script, without executing the function.

if __name__ == "__main__":
    print get_max_three_digit_product()
\$\endgroup\$
  • \$\begingroup\$ @hjpotter92 Yeah, just figured it out as well, see edit \$\endgroup\$ – Graipher Jan 17 '18 at 16:46
2
\$\begingroup\$

You already got some advice on coding style. however there is a big flaw in your algorithm which is not addressed by the accepted answer.

you try to iterate downward to get an effective implementation but you got the inner loop wrong. while you expect the outer loop to do few iterations your inner loop does check relatively low numbers early. you tried to limit that by stopping the iteration at 900, a magic value without reasoning. so your implementation may give wrong results as a pair of 901*901 is much smaller than a lot of untested pairs. you need at least a check if your product is bigger than the biggest untested one 999*900.

on the other hand if we do the inner loop right all problems are gone. we use the outer loop for the lower value and the inner loop for the greater one. we do not need an arbitrary limit any more and we are quite efficient.

for i in range(999,99,-1):
    for j in range(999,i-1,-1):
        # check palindrome

again we do not want to collect all palindromes but only the biggest one. we can abort safely when we cannot get a bigger product than the current maximum one.

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def get_biggest_palindrome():
    max_product = 0
    for i in xrange(999, 99, -1):
        if max_product >= 999*i:
            # no need to iterate further down
            break
        for j in xrange(999, i-1, -1):
            p = j * i
            if max_product >= p:
                # no need to iterate further down
                break
            if is_palindrome(p):
                max_product = p
    return max_product

I did some other minor changes:

is_palindrome - i like to name functions after what they return so the usage reads like a natural language sentence.

in python2 you should use xrange() instead of range() if you do not need a real list but just an iterator.

what you could do also:

make the magic numbers 999 and 99 constants and/or pass them as parameters. if it is about the number of digits you could define them as 10**(digits+1)-1, 10**digits-1 and pass digits as single parameter.

\$\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.