Project Euler #4 - Two-Headed Monster

Project Euler Series

This is a 4th post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 4th problem from Project Euler.
If you want to figure out a solution yourself, go to the Problem 4's page and come back later 😌

This time we have another very popular problem to solve. A palindrome, but with a nice twist. Usually, it's about strings and this one is about numbers.

It's going to be a short one, so let's get to it 😇

The Problem

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.

Am I a Palindrome?

Classic, simple algorithmic problem to solve. Is something the same when read from the beginning to the end as when read from the end to the beginning. As you can imagine, checking an integer is as simple as checking a single word 🤓

1. We need to change the input into a string.
2. When the input has an even length, then we simply divide it into two parts, otherwise we take the biggest even half from both sides.
3. If the left side is the same as reversed right side, we have a palindrome!

Show Me The Code!

Ok, ok, here you go 😇

fun isPalindromeNumber(value: Int): Boolean {
    val valueInString = value.toString()
    val valueSize = valueInString.length
    val comparisonCellLength = valueSize / 2
    val leftSide = valueInString.subSequence(
        startIndex = 0,
        endIndex = comparisonCellLength,
    )

    val rightSide = valueInString.subSequence(
        startIndex = valueSize - comparisonCellLength,
        endIndex = valueSize,
    ).reversed().toString()

    return leftSide == rightSide
}

Super simple ❤️

Glue Everything Together

In order to get the solution we need to use the isPalindromeNumber for every product of two numbers from $100$ to $999$ . Additionally, just out of curiosity, we can get an information how many palindromes has a given configuration.

fun getPalindromes(): List<Int> {
   val bottom = 100
   val top = 999

   val palindromes = mutableListOf<Int>()
   for (i in top downTo bottom) {
      for (j in top downTo bottom) {
         val result = i * j
         if (isPalindromeNumber(result)) {
            palindromes.add(result)
         }
      }
   }

   return palindromes
}

// Print the solution
println(getLargestPalindrome().maxOrNull())

The Solution

The answer to the problem is: 906609 and there are 2470 palindromes within the given setup.

Conclusion

Yet another classic problem to solve, however with a nice twist. That concludes the 4th problem. Nothing more interesting to share here. Just remember the set is created from a product of two numbers and not it's not a range from $100 * 100$ to $999 * 999$ .