## DEV Community Kunal Kamble

Posted on • Updated on

# Project Euler #4: Largest palindrome product

### 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 $N$ .

### Solution:

A palindrome is a number that reads the same both ways, like $121$ 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 $N$ , we can iterate over pre-calculated and sorted palindromes and return the first palindrome, which is less than $N$ .

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))