Project Euler - Problem 4 - Largest palindrome product

Find the largest palindrome made from the product of two `n`-digit numbers.

The problem

This is problem 4 from the Project Euler.

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 n-digit numbers.

A palindromic number?

This number must be the same number reversed. We will…

extract the last digit
multiply reversed number by 10 to shift left by 1
add the extracted digit to reversed
remove the last digit from temp

function is_palindrome(initial_number) {
  console.log('initial_number:',initial_number)
  var reversed = 0;
  var temp = initial_number;
  while (temp > 0) {
    var last_digit = temp % 10; // extract the last digit
    reversed = reversed * 10 + last_digit; // add last digit
    temp = parseInt(temp / 10); // remove last digit
    console.log(temp, reversed)
  }
  console.log('initial_number === reversed', initial_number, reversed, initial_number === reversed)
  console.log()
  return initial_number === reversed;
}

is_palindrome(9009)
is_palindrome(123321)
is_palindrome(123456)

Output:

initial_number: 9009
9
90
900
9009
initial_number === reversed 9009 9009 true

initial_number: 123321
1
12
123
1233
12332
123321
initial_number === reversed 123321 123321 true

initial_number: 123456
6
65
654
6543
65432
654321
initial_number === reversed 123456 654321 false

Thinking process…

The largest 2 digit number is 99, and the largest 3 digit number is 999, so we can get the largest number with 10^n -1.

Likewise, we can get the smallest n digit number with 10^n-1.

Let’s begin

Initialise variables and common functions:

// list of numbers we wanna test
var test_values = [2, 3];

// this function execute the code and records the time to execute
function run_function(func, test_values) {
  for(var i in test_values){
    console.log('Test value:', test_values[i]);
    var t0 = performance.now();
    console.log('Output:', func(test_values[i]));
    var t1 = performance.now();
    console.log("Took " + (t1 - t0) + " ms");
    console.log();
  }
}

// is_palindrome function to check number
function is_palindrome(initial_number) {
  var reversed = 0;
  var temp = initial_number;
  while (temp > 0) {
    var last_digit = temp % 10; // extract the last digit
    reversed = reversed * 10 + last_digit; // add last digit
    temp = parseInt(temp / 10); // remove last digit
  }
  return initial_number === reversed;
}

Attempt #1: brute force approach, not good

The idea is simple, 2 for-loops from the largest to smallest number, and compare every possible multiplication…

999 * 999
999 * 998
999 * 997
…
999 * 100
998 * 998
998 * 997
…
998 * 100
…
100 * 100

Tweaks to reduce computation

We will break out of the inner loop when we find a palindrome number. Because that will be the largest palindrome number for that outer loop.
In order not to multiply values that will be smaller than the current largest palindrome number, we update the smallest_number to current inner_i value to reduce the number of computation.

function largestPalindromeProduct(n) {
  return brute_force(n)
}

// the brute force approach, by for loop
function brute_force(n){
  var largest_number = Math.pow(10, n) -1;
  var smallest_number = Math.pow(10, (n-1));
  var largest_palindrome = 0;

  for(var outer_i=largest_number; outer_i>smallest_number; outer_i--){
    for(var inner_i=outer_i; inner_i>smallest_number; inner_i--){
      var number = outer_i * inner_i;
      if(is_palindrome(number) && number>largest_palindrome){
        largest_palindrome = number;
        if(inner_i>smallest_number){
          smallest_number = inner_i;
        }
        break;
      }
    }
  }
  return largest_palindrome;
}

run_function(largestPalindromeProduct, test_values);