Find the largest palindrome made from the product of two 3-digit numbers - Javascript

Yours doesn't work properly since it checks 999*999, then 999*998, then 999*997 until it reaches about 999*583. While it doesn't check 997*995 or something closer to the top which generates a larger number

function largestPalindrome(){

    var arr = [];    
    for(var i =999; i>100; i--){
        for(var j = 999; j>100; j--){
            var mul = j*i;
            if(isPalin(mul)){
                arr.push(j * i);
            }
        }
    }

    return Math.max.apply(Math, arr);
}

function isPalin(i){
    return i.toString() == i.toString().split("").reverse().join("");
}

console.log(largestPalindrome());

Here is another approach, store all palindrome generated by 3 numbers in an array, then use Math.max on the array to get the largest palindrome


I think if you apply maths to the problem you can decrease the guesswork really significantly.

I will write the three digit numbers as 1000 - a and 1000 - b which means the palindrome is 1 000 000 - 1000(a+b) + ab.

First, let's find solutions where ab < 1000. Then the three leftmost digits are 1000 - (a+b) and the three rightmost digits are ab.

Then I will say this is a palindrome with digits x,y,z:

100x+10y+z=ab
100z+10y+x=1000-a-b

thus

99x-99z = ab+a+b-1000
x-z = 1/99(ab+a+b-10)-10

So then (ab+a+b-10) is divisible by 99 and we also know that x and z being digits the left side is between -9 and 0 (the whole shebang is symmetrical so we can presume x <= z) so then 1/99(ab+a+b-10) is between 1 and 9. We can rewrite ab+a+b-10 as ab+a+b+1-11=99p so (a+1)(b+1)=99p+11=11*(9p+1) where p runs between 1 and 9. That's really easy:

for ($p = 1; $p <= 9; $p++) {
  $n = 9 * $p + 1;
  // This could be vastly optimized further.
  for ($j = 1; $j <= $n; $j++) {
    if ($n % $j === 0) {
      $a = 1001 - $n / $j;
      $b = 1001 - 11 * $j;
      $test = $a * $b;
      if (strrev($test) === (string) $test) {
        print "$a $b " . $a * $b . "\n";
      }
    }
  }
}

Now this prints only one solution which is the correct one.

Now we know 906609 is a solution so then is there a solution where ab > 1000 and 1000(a+b) - ab < 93391 ? There is not :)


As explained in @VisioN's comment:

995*583 = 580085 is a palindrome.

993*913 = 906609 is also a (larger) palindrome.

Your code checks 995*583 before 993*913 and exits at the first palindrome found, so it doesn't return the largest palindrome.

Solution: get the largest palindromes starting from 999*999 = 998001 downwards and check if they can be written as xyz*abc.

Or simply use the accepted solution from the question you linked :). Your solution, but instead of returning when you find the first palindrome, check if it is larger than the largest one already found, in which case you need to replace it. You can stop as soon as the largest palindrome is larger than i*999.

Tags:

Javascript