Project Euler Solution #4: Largest palindrome product

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.

Solution

First observation is that the number must be between \(100^2\) and \(999^2\) or in the range of \([10000, 998001]\). As the majority of numbers has 6 digits and we're looking for the largest, we ignore 5 digits numbers. Based on this, we can construct a palindromic number as:

\[ \begin{array}{rl} 'abccba' &= 100000a + 10000b + 1000c + 100c + 10b + a\\ &= 100001a + 10010b + 1100c\\ &= 11 (9091a + 910b + 100c) \end{array} \]

As such, we're looking for two largest numbers \(p, q\in\{x | 100 \leq x \leq 999\}\subset\mathbb{N}\) with:

\[p\cdot q =11 (9091a + 910b + 100c) \leq 999^2 \]

This equation shows us, that either \(p\) or \(q\), but not both must have a factor of 11. In order to maximize the two unknown, we start searching with \(p=999\) and for each decreasing \(p\), we search a maximum \(q\) to construct a palindrome. We can make an optmization based on the observation before: If \(p\) is not divisible by 11, \(q\) must be, and as such we can start searching with 990 as the largest multiple of 11 and search only for multiples of 11. Another optimization is, that we don't need to let \(q\) go below \(p\) since we can interchange the numbers. An implementation can then look as follows:

function solution() {

    var r = 0;

    for (var s, q, p = 999; p >= 100; p--) {

        if (p % 11 === 0) {
            q = 999;
            s = 1;
        } else {
            q = 990;
            s = 11;
        }

        for (; q > 99; q -= s) {

            var t = p * q;

            if (r < t && isPalindrome(t)) {
                r = t;
                break;
            }
        }
    }
    return r;
}

Okay that's good. But why not reversing \(p, q\) again. We could loop \(p\) from 990 through the multiples 11 and use \(q\) to match a palindrome. Adding another condition to break the inner loop early reduces the search space about 42 times.

function solution() {

  var r = 0;

  for (var p = 990; p > 99; p-= 11) {

    for (var q = 999; q > 99; q--) {

      var t = p * q;

      if (r < t && isPalindrome(t)) {
        r = t;
        break;
      } else if (t < r) {
        break;
      }
    }
  }
  return r;
}

For the hackerrank implementation, a parameter \(N\) is needed, which limits the maximum number. This simply changes the central condition to \(r < t < N \land \text{ isPalindrome}(t)\). Furthermore, the solution utilizes a simple helper function to check if a number actually is a palindrome:

function isPalindrome(x) {

    var n = 0;
    var m = x;

    while (x > 0) {
        n = n * 10 + x % 10;
        x = x / 10 | 0;
    }
    return n === m;
}