Skip to main content

Problem 4 Project Euler Solution with Python

Largest Palindrome Number

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.?

 To solve this problem I first wrote a program which was as follows:
#Time module
import time

#time at start of program
start = time.time()

#Function to check if number is palindrome
def isPalindrome(n):
 number = str(n)
 reverse_number = ''
 for k in number:
  reverse_number = k + reverse_number
 if reverse_number == number:
  return True
 return False

#largest_palindrome
largest_palindrome = 0

#For loop to generate multiples
for i in range(1000,100,-1):
 for j in range(1000,100,-1):
  number = i*j
  if number > largest_palindrome:
   if isPalindrome(number):
    largest_palindrome = number
#Printing the largest palindrome
print largest_palindrome

#Printing the time of execution
print time.time()-start
  I think the above program is pretty easy to understand also the time for the execution was less than 1 second. But I was not satisfied and wanted more faster program.

 My first idea was to eliminate the function isPalindrome so that the time for calling the function is reduced throughout the iterations. But as isPalindrome checked if the reverse of the number was the number, so to remove it if I had checked directly the reverse of the number using the if statement, then I would be able to remove isPalindrome and also it would reduce the time of execution.

 Because of using the reverse string operation and eliminating the isPalindrome function, time for execution of the code reduced by staggering 90%(approximately).

Program

I would like to explain the for loop block of code which is pretty interesting.

 We will consider the example given in the question.

 Before the starting of the code the value of the largest_palindrome1 is 0.

 Now in the first iteration the value of i is 100 and at next lever the value of j is 100.

 The if statement is True because the value of i*j which is 100*100 = 10000 is greater than 0.

 In the next line we have used the string extended Slice operation to generate the reverse of the given number.

 If the reverse is same then the number is palindrome. Also we have already checked if i*j is larger than largest_palindrome1, and so there is no need to check it again. In the present iteration (i=100, j=100), this condition doesn't execute and the if loop exits.

 In the similar way the if loop checks if the number is palindrome and also if the number is larger than the previous value of largest_palindrome1, then the value of largest_palindrome1 is changed.

 break has been used because it is un necessary to continue looping as we have found the largest palindrome number(This case is only true when we are iterating from 100 to 1 or 1000 to 1).

 If you want to download the above program then you can download it from Github Gist

Output

Summary

I think this problem is also easy to solve but making it run at much shorter time was challenging. The execution time was around 0.01s which is small. But if you have any program whose execution time is less than the above program, please do share it with me so that it will be helpful for the community.

 I think the code is pretty easy to understand because it has been commented properly. Also I have explained some part of the code. But if you have any doubt or didn't understand anything then please do comment in the comment box below and I will be glad to help you.

 You can also contact me if you want.

 If you have any suggestions or found any typo which I made, then please do let me know so that we can improve and help the community.

 I would like to thank the Stackoverflow community, which helped me in reducing the execution time.
Jason has also written a very good solution for this question but the execution time was more than mine😋!

Thank you. Have a nice Day😃.
Labels:

Popular posts from this blog

Making a quiz web app with python and flask

Edit : When you are creating a web app with h tml templates, then y ou will have to sa ve the html file in templates folder in the Current Wor ki ng Directory( CWD). If you save the file in the C W D directl y you will get a TemplateNotFound error. Thank you Udhay for pointing it out.   In this post we will create a quiz website using python . I will be using the flask framework . After reading this tutorial you will learn form submission , flask templates , python code in flask templates , shuffling the questions and options with the random module and few others.  Please note that this tutorial is not big as it seems to be. Some of the code has been rewritten to maintain consistency and also font size is somewhat big so that your eyes won't get stressed reading this tutorial. Also the content has not occupied the full width of the page. In this tutorial I am assuming that you are having a very basic understanding of the flask framework . Please refer the documentation
Read more

Problem 11 Project Euler Solution with python

Largest product in a grid In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07
Read more

Problem 60 Project Euler Solution with python

Prime pair sets The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime. This problem is j u st a brute force problem. If you have come here because you don't know the limit upto which you will h ave to gener ate the prime numbers t hen go ahe ad and t r y with 10,000 . When I first start ed solving the problem I chose 1 million(beca use most of the problem s on project E uler have this limit ), but it took very long for the computer to fin d the solution. After searching on the internet then I found many people choosing 10, 000 so I have changed my in put f rom 1 million to 10000 and the output was f ast. He
Read more