Project Euler: Problem 4

Posted on November 14th 2020 in Algorithms by Pim Debaere.

Project Euler: Problem 4

Time for a new problem, and a possible solution, from Project Euler: searching for palindromic numbers. As always, stop reading if you want to find the solution yourself.

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.
Problem 4

The easiest way is to go through all possible products and see if the number is a palindrome. I do the check by splitting the number in an array and returning and merging this array. In other programming languages there could be a method for this, in JavaScript unfortunately not (yet). In PHP, for example, you can use strrev for this.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function largestPalindromeProduct(lower, upper) {
  var ret = 0;
  var product = 0;
  
  for (var i = lower; i <= upper; i++) {
    for (var j = lower; j <= upper; j++) {
      product = i * j;

      if (ret < product &&
          product.toString() === product.toString().split('').reverse().join('')) {
        ret = product;
      }
    }
  }

  return ret;
}

console.time('run');
var answer = largestPalindromeProduct(100, 999);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 28ms
// Answer: 906609

Fig. 1 – Project Euler: Problem 4 - loop through all possible products.

As you can see in the piece of code above, we are dealing with all possible combinations of two factors i and j. When its product is larger than a previous product, we check whether it is palindromic. It is immediately noticeable that this is not that fast: 28ms.

If we think logically, this should go a bit faster if we start at the upper limit instead of the lower limit. In this way we have the largest product faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function largestPalindromeProduct(lower, upper) {
  var ret = 0;
  var product = 0;
  
  for (var i = upper; i >= lower; i--) {
    for (var j = upper; j >= lower; j--) {
      product = i * j;

      if (ret < product &&
          product.toString() === product.toString().split('').reverse().join('')) {
        ret = product;
      }
    }
  }

  return ret;
}

console.time('run');
var answer = largestPalindromeProduct(100, 999);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 8ms
// Answer: 906609

Fig. 2 – Project Euler: Problem 4 - loop through all possible products descending.

And indeed, once we adjust the for loops to count down, we're already winning 20ms! But it can be even more efficient, because with the above function we do the same calculations twice. For example, we once have i = 101 and j = 202, but also once i = 202 and i = 101. If we nip this in the bud, we obtain a function that achieves the desired result even faster. At the same time, we can also jump out of the middle for loop when the product is smaller than an already found product – since for further values of j this can never be greater.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function largestPalindromeProduct(lower, upper) {
  var ret = 0;
  var product = 0;
  var i, j;
  
  for (i = upper; i >= lower; i--) {
    for (j = upper; j >= i; j--) {
      product = i * j;

      if (product < ret) {
        break; // product will always be too small now
      }

      if (product.toString() === product.toString().split('').reverse().join('')) {
        ret = product;
      }
    }
  }

  return ret;
}

console.time('run');
var answer = largestPalindromeProduct(100, 999);
console.timeEnd('run');
console.log('Answer: ' + answer);

// output:
// run: 5ms
// Answer: 906609

Fig. 3 – Project Euler: Probleem 4 - more efficient solution to the problem.

With a little bit of logical thinking, we have thus obtained a function that is almost six times faster.