1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ No, I don't want to use tricks here return (s == s[::-1]). Thanks! \$\endgroup\$ – CodeYogi Sep 28 '15 at 7:22
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Dan Pantry Sep 28 '15 at 7:25
  • \$\begingroup\$ @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 \$\endgroup\$ – spyr03 Sep 28 '15 at 9:17
  • \$\begingroup\$ 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. \$\endgroup\$ – Jaime Sep 28 '15 at 11:38
  • \$\begingroup\$ yeah - you're right about that. Let me see if I can find a way to iterate where you can return early. \$\endgroup\$ – ErikR Sep 28 '15 at 12:51
-1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Schneider Sep 28 '15 at 15:21
  • \$\begingroup\$ @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 \$\endgroup\$ – Caridorc Sep 28 '15 at 15:42
  • \$\begingroup\$ @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. \$\endgroup\$ – CodeYogi Sep 29 '15 at 4:11
  • \$\begingroup\$ @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 \$\endgroup\$ – Caridorc Sep 29 '15 at 12:32

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.