Links: Project Euler, HackerRank
Problem statement:
We need to find the largest palindrome made by the product of two 3-digit numbers, and for HackerRank, we need to find the largest palindrome with similar circumstances but is less than .
Solution:
A palindrome is a number that reads the same both ways, like is identical in both ways, right-to-left (normal) and left-to-right (reverse).
So to detect if a number is a palindrome or not, we could check if the number is equal to its reverse if it is, then it's a palindrome, and if not, it's not. To reverse a number, we can pop the last digit of the number and push it to the first of the new number (which will be the reverse number) repetitively.
def is_palindrome(x: int) -> bool:
"""
Checks if the given number is a palindrome or not.
"""
x1 = x
rev = 0
while x1 != 0:
rev *= 10
rev += x1 % 10
x1 //= 10
return rev == x
Now for the HackerRank problem, it will be easier to pre-compute all possible palindromes and sort them initially. We can generate every product of 3-digit numbers and add it to the palindromes list if the product is a palindrome.
def _calculate_palindromes(self):
palindromes = []
for three_digit_number_a in range(100, 1000):
for three_digit_number_b in range(three_digit_number_a, 1000):
product = three_digit_number_a * three_digit_number_b
if is_palindrome(product):
palindromes.append(product)
self._palindromes = sorted(palindromes, reverse=True)
To find the largest palindrome below
, we can iterate over pre-calculated and sorted palindromes and return the first palindrome, which is less than
.
def below(self, n: int) -> int:
"""Returns largest palindrome less than or equal to n"""
for palidrome in self._palindromes:
if palidrome < n:
return palidrome
return None
The final Hackerrank code will look something like this:
#!/bin/python3
import sys
def is_palidrome(n: int) -> bool:
n1 = n
rev = 0
while n1 != 0:
rev *= 10
rev += n1 % 10
n1 //= 10
return rev == n
class PalidromeHelper:
"""
Precalculates all possible palindromes generated by-product of 3-digit numbers.
"""
_palindromes = []
def __init__(self):
self._calculate_palindromes()
def _calculate_palindromes(self):
palindromes = []
for three_digit_number_a in range(100, 1000):
for three_digit_number_b in range(three_digit_number_a, 1000):
product = three_digit_number_a * three_digit_number_b
if is_palidrome(product):
palindromes.append(product)
self._palindromes = sorted(palindromes, reverse=True)
def below(self, n: int) -> int:
"""Returns largest palidrome less than n"""
for palidrome in self._palindromes:
if palidrome < n:
return palidrome
return None
helper = PalidromeHelper()
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
print(helper.below(n))
For the ProjectEuler problem, we need to find the largest possible palindrome, so in that case, we can pass math.inf in below method.
if __name__ == "__main__":
helper = PalidromeHelper()
print(helper.below(math.inf))
Thank you for reading.
Top comments (0)