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

https://projecteuler.net/problem=4

Digits Array

First let’s us create a function that splits a number into digits. There are several ways to do this.

Converting to a string, splitting, and parsing back to int.

function digits(n) {
  return (n + '').split('').map(Number);
}
timer(digits, 100000, 1234567);
// digits x 100000: 108.805ms
// [1, 2, 3, 4, 5, 6, 7]

Using mod and division to lop off the 1’s digit.

function digits(n) {
  var digits = [];
  while(n) {
    digits.push(n % 10);
    n = Math.floor(n / 10);
  }
  return digits.reverse();
}
timer(digits, 100000, 1234567);
// digits x 100000: 18.828ms
// [1, 2, 3, 4, 5, 6, 7]

Palindromic

To check if a number is palindromic, we will copy the digits array and reverse the array and check if the values are still equal. Instead of iterating, each element to check for equality we will use a hack and join the array into a string.

function isPalindromic(n) {
  var d = digits(n),
      reversed = d.slice().reverse();
  return d.join('') === reversed.join('');
}
timer(isPalindromic, 100000, 1234567);
// isPalindromic x 100000: 314.782ms
// false

timer(isPalindromic, 100000, 1234321);
// isPalindromic x 100000: 331.178ms
// true

Another way to check if a number is palindromic is to reverse all the digits and see if they are the same. Let’s give that way a shot.

function isPalindromic(n) {
  if (n < 0) throw 'isPalindromic only works for positive numbers.';
  if (Math.floor(n / 10) === 0) return true; // Single digit numbers are palindromic.
  if (n % 10 === 0) return false; // n > 0, without leading 0s cannot be palindromic if ending in 0.

  var number = n,
      reversed = 0;
  while (number) {
    reversed *= 10;
    reversed += number % 10;
    number = Math.floor(number / 10);
  }
  return reversed === n;
}
timer(isPalindromic, 100000, 1234567);
// isPalindromic x 100000: 12.493ms
// false

timer(isPalindromic, 100000, 1234321);
// isPalindromic x 100000: 11.089ms
// true

Much faster! We will use this version for our brute force solution.

Domain

We want to find the largest palindrome made from the product of two 3-digit numbers. The smallest 3-digit number is 100. The largest 3-digit number is 999.

This means that the number we are looking for is the range of $[100\times100\,,999\times999]$, or $[10,000\,,998,001]$.

We can find this number by brute force by multiplying each number between 100 and 999 with every number between 100 and 999.

Instead of having two nested for loops going from min to max, the inner loop can be set to start at the current outer loop value. This will prevent us from calculating those values twice. For example: when the outer loop is at 101, if the inner loop started at 100, that value would have already been calculated when the outer loop was at 100 and the inner loop was at 101.

Brute Force

function euler4() {
  var min = 100,
      max = 999,
      answer = 0;
  for (var i = min; i <= max; i++) {
    for (var j = i; j <= max; j++) {
      var product = i*j;
      if (product > answer && // Check palindromic for products > current answer.
          isPalindromic(product)) {
        answer = product;
      }
    }
  }
  return answer;
}
timer(euler4);
// euler4 x 1: 3.493ms
// 906609