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