Project Euler #4 "Largest Palindrome product" in Python Given


  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.


Solution

import time

def reverse(num):
    dreverse = 0
    while (num &gt; 0):
        dreverse = dreverse * 10 + num % 10
        num /= 10
    return dreverse

def is_palindrome(num):
    if (num &lt; 0):
        raise ValueError('Non-negative integers only')
    return num == reverse(num)

def main():
    largest_palindrome = 0
    lower = 999
    while lower &gt;= 100:
        upper = 999
        while upper &gt;= lower:
            if upper * lower &lt;= largest_palindrome:
                break
            if is_palindrome(upper * lower):
                largest_palindrome = upper * lower
            upper -= 1
        lower -= 1
    return largest_palindrome

start_time = time.time()
print main()
print("--- %s seconds ---" % (time.time() - start_time))
o/p: 906609
--- 0.0150721073151 seconds ---     


I am including timing metric from now on. This solution seems \$O(N^2)\$. Can I improve it further?
You are recomputing the product upper * lower three times:

    while upper &gt;= lower:
        if upper * lower &lt;= largest_palindrome:
            break
        if is_palindrome(upper * lower):
            largest_palindrome = upper * lower


You should save it in a variable:

    while upper &gt;= lower:
        product = upper*lower
        if product &lt;= largest_palindrome:
            break
        if is_palindrome(product):
            largest_palindrome = product


Also, how about this version of is_palindrome:

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


Update

Replace your loops with for and xrange:

largest = 0
for lower in xrange(999,99,-1):
    for upper in xrange(999,lower-1,-1):
        ...


It makes the intent of your code a lot clearer, and it is easier to correctly write the loop.

(The following is note quite right)

Finally, if upper*lower &lt;= largest_palindrome, you actually return from the function:

        if upper * lower &lt;= largest_palindrome:
            return largest_palindrome


The return will essentially break out of both while loops. Using just break will only break out of the inner loop. Of course, the remaining cases will execute very quickly since they will only last one iteration of the inner loop, but it is still a good optimization to know about.