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
.