# 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 > 0):
dreverse = dreverse * 10 + num % 10
num /= 10
return dreverse

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

def main():
largest_palindrome = 0
lower = 999
while lower >= 100:
upper = 999
while upper >= lower:
if upper * lower <= 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 >= lower:
if upper * lower <= largest_palindrome:
break
if is_palindrome(upper * lower):
largest_palindrome = upper * lower


You should save it in a variable:

    while upper >= lower:
product = upper*lower
if product <= 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 <= largest_palindrome, you actually return from the function:

        if upper * lower <= 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.

• No, I don't want to use tricks here return (s == s[::-1]). Thanks! Sep 28, 2015 at 7:22
• How is this a trick? s == s[::-1]evaluates true if s is equal to the reverse of s, and evaluates false if it isn't. This is exactly what a palindrome is. That's actually exactly what your code already does, but this does it in a more concise manner.
– Dan
Sep 28, 2015 at 7:25
• @ARedHerring An explanation of how it works might be more convincing. CodeYogi The "trick" is that s[::-1] iterates from the end of the variable to the start. It what the division and mod code does, but it is easier to read Sep 28, 2015 at 9:17
• The suggestion to replace break with return has faulty logic, I'm afraid, e.g. if the product of lower = 500, upper = 501 is the first smaller than largest_palindrome, we still need to check lower = 499, upper = 999, which is about 2x larger. Sep 28, 2015 at 11:38
• yeah - you're right about that. Let me see if I can find a way to iterate where you can return early. Sep 28, 2015 at 12:51

I am going to suggest a solution that is 20x less perfomant than yours, because Python was really made to optimize programmer's time, not execution time. It should be noted that my solution is still under a second of execution time.

def is_palindrome(string):
return string == ''.join(reversed(string))


A number is just a kind of string, so I wrote a more general (and, yes, slower) function to check for palindromes. The number should be converted to string before being passed in to the function.

The main body of this program is really close to natural langauge, it is just:

print(max(i * j for i in range(500, 999) for j in range(500, 999)
if is_palindrome(i * j)))


it uses a generator expression, so the usage of memory is O(1) and the time complexity is O(N^2) as in your solution.

Almost all the time is spent in the is_palindrome function, using your function would make this as fast as your solution.

• Just to be pythonic isn't an excuse for not using the best algorithm. In your variant, you have to evaluate is_palindrome() for every value. CodeYogi and user5402 break out of the inner loop as soon as lower*upper is less then the currently known best value. This reduces the number of calls to is_palindrome down by a factor of 66. Also, in my eyes is s==s[::-1] much more readable. Sep 28, 2015 at 15:21
• @PeterSchneider indeed, this is just an alternate way that preferes a slower algoritmh for simplicity of implementation, it is different but by no means better Sep 28, 2015 at 15:42
• @Caridorc I agree with @peter that in the same of being pythonic we are really writing less efficient code. This is my real experience. If we can improve the performance then why the hell we use slower techniques in the name of readablilty? Or there should be strict disclaimer for python learners Learn at your own risk because you won't pass any coding competitions . A code is beautiful when it runs not when its dead. Sep 29, 2015 at 4:11
• @CodeYogi You are raising an interesting point, Should a code be 20x slower just to be more readable? Yes and no, and the answer changes from case to case Sep 29, 2015 at 12:32