DEV Community

Cover image for Project Euler #4: Largest palindrome product
Kunal Kamble
Kunal Kamble

Posted on • Updated on

Project Euler #4: Largest palindrome product

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

Solution:

A palindrome is a number that reads the same both ways, like 121121 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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

To find the largest palindrome below NN , we can iterate over pre-calculated and sorted palindromes and return the first palindrome, which is less than NN .

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
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

Thank you for reading.

Oldest comments (0)