Project Euler Problem 4

Largest Palindrome Product

Project Euler presents the following Problem #4:

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.

First things first, let's decide how to determine whether a value is a palindrome.

Palindrome Check

Even though we're dealing with numbers in this problem (and future ones), I've chosen to perform the check as an extension function on String, so that we can explore the different options and avoid any need to create overrides for Int, Long & BigInteger numbers.

The simplest option is to use the built-in function reversed().

1// Built-In
2fun String.isPalindrome() = this == this.reversed()

The next option is a manual implementation that compares the outermost characters by iterating through only half the size of the calling String.

1// Manual
2fun String.isPalindrome(): Boolean {
3    for (i in 0 until length / 2) {
4        if (this[i] != this[lastIndex - i]) return false
5    }
6    return true
7}

The manual option can be converted from an iterative implementation to a recursive one by repeatedly calling the same function on a smaller String that has had its first and last characters removed, until the String is either too small or the characters being checked are unequal.

1// Recursive
2fun String.isPalindrome(): Boolean {
3    return when {
4        length < 2 -> true
5        first() != last() -> false
6        else -> substring(1, lastIndex).isPalindrome()
7    }
8}

1public static final boolean isPalindrome(@NotNull String $this$isPalindrome) {
2      while(true) {
3         Intrinsics.checkNotNullParameter($this$isPalindrome, "$this$isPalindrome");
4         boolean var10000;
5         if ($this$isPalindrome.length() < 2) {
6            var10000 = true;
7         } else {
8            if (StringsKt.first((CharSequence)$this$isPalindrome) == StringsKt.last((CharSequence)$this$isPalindrome)) {
9               byte var2 = 1;
10               int var3 = StringsKt.getLastIndex((CharSequence)$this$isPalindrome);
11               String var4 = $this$isPalindrome.substring(var2, var3);
12               Intrinsics.checkNotNullExpressionValue(var4, "this as java.lang.String…ing(startIndex, endIndex)");
13               $this$isPalindrome = var4;
14               continue;
15            }
16            var10000 = false;
17         }
18         return var10000;
19      }
20}

1public static final boolean isPalindrome(@NotNull String $this$isPalindrome) {
2      Intrinsics.checkNotNullParameter($this$isPalindrome, "$this$isPalindrome");
3      boolean var10000;
4      if ($this$isPalindrome.length() < 2) {
5         var10000 = true;
6      } else if (StringsKt.first((CharSequence)$this$isPalindrome) != StringsKt.last((CharSequence)$this$isPalindrome)) {
7         var10000 = false;
8      } else {
9         byte var2 = 1;
10         int var3 = StringsKt.getLastIndex((CharSequence)$this$isPalindrome);
11         String var4 = $this$isPalindrome.substring(var2, var3);
12         Intrinsics.checkNotNullExpressionValue(var4, "this as java.lang.String…ing(startIndex, endIndex)");
13         var10000 = isPalindrome(var4);
14      }
15      return var10000;
16}

What if we didn't want to cast the number to a String? Because reasons.

In that case, we could use a method similar to the first built-in function. A reversed number would be created by repeatedly removing the right-most digit of the original number and adding it to the new number (adjusted to the correct multiple of 10). This reversed number would then be compared to the original for equality.

1// No Cast
2fun Long.isPalindrome(): Boolean {
3    if (this < 10) return true
4    var original = this
5    var reversed = 0L
6    while (original > 0L) {
7        reversed = reversed * 10L + original % 10L
8        original /= 10L
9    }
10    return this == reversed
11}

There are probably other more clever ways to code a palindrome check but these four are a solid start, so let's see how they compare.

I ran a benchmark test using a 19-digit palindrome "1234567890987654321" (or a Long for the last function) over 1 million iterations and got the following average execution times on my system:

The choice is yours to plug in whatever palindrome check you've chosen or created yourself, but the solutions in the next section will use the manual implementation of String.isPalindrome() behind the scenes.

1def is_palindrome(n: str) -> bool:
2    return n == n[::-1]

Brute Force

The first solution simply iterates through all products of 3-digit numbers and stores the product if it is both greater than the current stored maximum and a palindrome.

1fun largestPalindromeProductBrute(): Int {
2    var largest = 0
3    for (x in 101..999) {
4        for (y in x..999) {
5            val product = x * y
6            if (product > largest && product.toString().isPalindrome()) {
7                largest = product
8            }
9        }
10    }
11    return largest
12}

Line 3: The lower limit of the x loop ignores 100, since a product using this value would not be able to create a palindrome unless leading zeroes were allowed.

Line 4: The commutative property of multiplication allows us to avoid redundancy in our loops, as, for example, $100*999=999*100$. Setting the current value of x as the lower limit of the nested y loop avoids these duplicate products.

Line 6: Depending on your choice of String.isPalindrome(), this invocation may be considered an expensive operation (if you're casting from a number to a string, it probably is), especially relative to the comparison product > largest. Whenever a conditional branch like this is presented, it is more efficient to take advantage of the short-circuit evaluation that the && operator provides (not to be confused with the infix logical operator and() from the Boolean class). Don't reverse the order of this clause.

This solution works just fine, but we can do better. As a tool for comparison, I added two counters to the code: one for every time a product was initialized, and another for every time String.isPalindrome() was called.

📊 largestPalindromeProductBrute() created 404,550 products and checked 50,404 of those products for a palindrome.

Brute Force - Backwards

Whenever the goal of a problem involves finding the largest or maximum value, and an upper limit is either known or reasonably assumed, it can be more logical to start at that upper limit and work backwards. In this solution, we perform a very similar iteration as the first one except in the reverse order.

The nested y loop is still optimized to avoid duplicates with the current value of x being used as its lower limit. The major advantage moving backwards provides is that the nested y loop can now be broken early, making it more efficient.

1fun largestPalindromeProductBackwards(): Int {
2    var largest = 0
3    outer@for (x in 999 downTo 101) {
4        for (y in 999 downTo x) {
5            val product = x * y
6            if (product <= largest) continue@outer
7            if (product.toString().isPalindrome()) {
8                largest = product
9                break
10            }
11        }
12    }
13    return largest
14}

Line 6: We are only interested in finding the largest product. So, if a value of y, when multiplied with current x, gives a product that is not greater than the stored maximum, there is no point in continuing to decrement y. Instead, we break out of the inner loop and start the outer loop with a new x.

Line 7: Any product that reaches this line in the codeblock will have to be greater than largest, so the only conditional needed is a palindrome check.

Line 9: If a palindrome is found, the inner loop can be terminated because y will continue to get smaller. So, any other palindromes found with current x will be smaller in value.

1fun largestPalindromeProductBackwards(): Int {
2    var largest = 0
3    for (x in 999 downTo 101) {
4        for (y in 999 downTo x) {
5            val product = x * y
6            if (product <= largest) break
7            if (product.toString().isPalindrome()) {
8                largest = product
9                break
10            }
11        }
12    }
13    return largest
14}

📊 largestPalindromeProductBackwards() created 4047 products and checked 3225 of those for a palindrome. That's approximately 99% fewer products compared to the first brute force solution!

But guess what? We can still do better 🤯

Optimized Solution

The product of two 3-digit integers can be at most six digits long. It can also be shown with some algebra that, to produce a 6-digit palindrome, one of the 3-digit integers must have a factor of 11.

Given a 6-digit palindrome ($P$) with 3 mirrored digits, $x,\;y,\;z$, the following formula matches every palindrome within those constraints:

So instead of iterating through all possible combinations as per the first brute force solution (which confirmed that the answer we seek has six digits and not five), this formula allows us to only visit combinations in which x is a multiple of 11.

1fun largestPalindromeProduct(): Int {
2    var largest = 0
3    for (x in 990 downTo 110 step 11) {
4        for (y in 999 downTo 101) {
5            val product = x * y
6            if (product <= largest) break
7            if (product.toString().isPalindrome()) {
8                largest = product
9                break
10            }
11        }
12    }
13    return largest
14}

Line 4: Limiting x to only multiples of 11 means removing the usual limit on y that avoids duplicates, as setting current x as the lower limit of y would cause some valid product combinations to be skipped.

📊 largestPalindromeProduct() created 1626 products and checked 1550 of those for a palindrome. That's a decent reduction in operations compared to both brute force solutions.

Alternative Solution

But what if your initial thought process was to iterate backwards through only palindromes then check if each could be formed as a valid product of two 3-digit integers?

The largest product of two 3-digit integers is $999*999=998001$, so the largest palindrome below this upper limit is $997799$.

Rather than using a palindrome check, this solution uses a helper function Int.toPalindrome() that generates the next palindrome for every iteration backwards from 997. The first palindrome found to be a valid product would be the expected result and the loop would be terminated after only 92 iterations.

1import kotlin.math.sqrt
2
3fun largestPalindromeProductAlt(): Int {
4    val largest: Int
5    var num = 997
6    while (true) {
7        val palindrome = num.toPalindrome()
8        if (palindrome.is3DigProduct()) {
9            largest = palindrome
10            break
11        }
12        num--
13    }
14    return largest
15}
16
17fun Int.toPalindrome(): Int {
18    return this * 1000 + this % 10 * 100 + this / 10 % 10 * 10 + this / 100
19}
20
21fun Int.is3DigProduct(): Boolean {
22    for (factor1 in 999 downTo sqrt(1.0 * this).toInt()) {
23        if (this % factor1 == 0 && this / factor1 in 101..999) return true
24    }
25    return false
26}

Int.is3DigProduct() tries to find two 3-digit factors ($a$ and $b$) of a palindrome integer ($p$) based on the following premise:

Speed Comparison

A benchmark test over 1000 iterations returned the following execution times on my system:

The optimized solution performed as expected based on the reduction in loop iterations but the speed of the alternative solution was an interesting output.

Visit the following links to see the Kotlin and Python source code and test suites in their respective repositories:

• Kotlin source: solution tests
• Python source: solution tests

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🐍🌉🐍🏝️