Largest palindrome product in Javascript

Question

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.

i made this code to find the solution but the answer in Project Euler website still incorrect:

function Palindromic(x) {
    var pal = parseInt(x.toString().split('').reverse().join(''));

    if (pal === x)
        return true;
    else
        return false;
}

var x = 100,
    y = 100,
    product = x * y;

for (x; x <= 999; x++) {
    for (y = x; y <= 999; y++) {
        product = x * y;
        if (Palindromic(product)) {
            console.log(x + '*' + y + '=' + product);
        }
    }
}

Is there a problem in my code?! anyway, the answer that i got was 888888 from 924*962

Answer 1

To make finding large palindromes early more likely, you can count downwards from the last number of the range, instead of upwards from the first number of the range.

This way you can stop checking factors that would be too small to improve upon the largest palindrome found so far, breaking the inner loop early.

For example:

/**
 * Check if a number is a palindrome.
 * @param {number} num Number to be checked.
 * @returns {boolean} True if the number is a palindrome, false otherwise.
 */
const isPalindrome = (num) => {
  const numStr = String(num)
  const reverseNumStr = [...numStr].reverse().join('')
  return numStr === reverseNumStr
}

/**
 * Find the largest palindrome product of two n-digit numbers.
 * @param {number} digits Number of digits of the multiplied numbers.
 * @returns {number} Largest palindrome product.
 */
const largestPalindromeProduct = (digits) => {
  const start = 10 ** (digits - 1) // first n-digit number
  const end = (10 ** digits) - 1 // last n-digit number
  let max = 0

  for (let factorA = end; factorA >= start; factorA--) {
    for (let factorB = end; factorB >= factorA; factorB--) {
      const product = factorA * factorB
      if (product <= max) break
      if (isPalindrome(product)) max = product
    }
  }

  return max
}

The official Project Euler problem 4 overview goes over this and other optimizations.

Answer 2

let string = [];
let mul = 0;

let x = 100;
while(x < 1000){
    for(y = 100; y < 1000; y++){
        mul = x * y;
        let n = mul.toString();                   //to convert multiplied value to string 
        let stringSplit = n.split("");            //splits the string in array
        let reverseSplit = stringSplit.reverse(); //reverse the string array
        let joinSplit = reverseSplit.join("");    //join the reversed array into string
        if (joinSplit == n){          //check weather reversed string is equal to multiplied value
            string.push(joinSplit);  //as there are lots of value it puts them in array
        }
    }
  x++;
 }
 string.sort(function(a, b){return b-a}); // sort array in descending order as we want highest value 
 console.log(string[0]); 

Answer 3

Also a late answer but looping through all options is really slow. You can loop through batches, for n===2, you can do batches of 10, for n ===3 batches of 100 and so on

here is a JSPerf https://jsperf.com/largest-palindrome-product/1

export const isPalindrome = (arg: string | number): boolean => {
  const orig = `${arg}`;
  const reverse = orig.split("").reverse().join("");

  return orig === reverse;
};

/**
 * The idea here is to search in batches to avoid looping trough all of the possibilities.
 *
 * For n === 2 you will first search between 90 and 99 if no palindrome found you will move to 80 and 89 etc.
 * If a palindrome is found you will pick the max from the batch
 *
 */
export const largestPalindromeProduct = (num: number): [number, [number, number]] => {
  const min = Number("1".padEnd(num, "0"));
  const max = Number("9".padEnd(num, "9"));

  let stepperMax = max;
  let res: number = 0;

  let position: [number, number] = [min, min];

  while (stepperMax >= min) {
    for (let i = max; i >= stepperMax - min - 1; i--) {
      for (let j = max; j >= stepperMax - min - 1; j--) {
        const temp = i * j;
        if (isPalindrome(temp) && temp > res) {
          position = [i, j];
          res = temp;
        }
      }
    }

    if (res !== 0) {
      return [res, position];
    }

    stepperMax = stepperMax - min - 1;
  }

  return [res, position];
};

Answer 4

Very late answer, my approach was similar to Sirko. I found what I consider an interesting way to get a dramatic performance boost, so I thought I'd share:

function isPalindrome(num) {
  return parseInt(String(num).split('').reverse().join('')) === num;
}

function findLargestPalindromeProduct(numberOfDigits) {
  var start = Math.pow(10, numberOfDigits - 1);
  var end = Math.pow(10, numberOfDigits);
  var largestPalindrome = 0;
  var product;
  for (a = start; a < end; a++) {
    for (b = start; b < end; b++) {
      product = a * b;
      if (largestPalindrome < product) {
        if (isPalindrome(product)) {
          largestPalindrome = product;
        }
      }
    }
  }

  return largestPalindrome;
}
console.time('Function #1');
for (var i = 0; i < 100; i++) {
  findLargestPalindromeProduct(3);
};
console.timeEnd('Function #1')

I get an average of about 34ms per iteration when I run that in the Chrome console.

When I check if it's a palindrome first, my average iteration was around 500ms.

The reason it is so much faster is because checking if the product is greater than the largestPalindrome is extremely fast to check and filters out many of the pairs quickly, as opposed to checking if it's a palindrome first (when it might not even be larger than the largestPalindrome - even if it is in fact a palindrome).

Answer 5

This is a very late answer, however I propose a different approach, its a sufficient solution, not perfect solution

I only checked for 6 digit palindrome.

1.Generate only palindrome 6 digit number from max (first three digit, should be reversed last three digit)

2.Check whether the generated palindrome digit has two 3 digit number as factor, if yes return the number, that is the largest palindrome that can be produced by two 3 digit number product. Code sample in c#.

    static void Main(string[] args)
    {
        Console.WriteLine(SixDigitPalindromeWithDivisor().ToString());
        Console.ReadLine();
    }

    public static int SixDigitPalindromeWithDivisor()
    {
        for (int i = 999; i > 100; i--)
        {
            //generating palindrome number from max
            var palindromeInt = Int32.Parse(Convert.ToString(i) + ReverseString(Convert.ToString(i)));

            //checking three digit number factor exist
            if (CheckThreeDigitDivisorExists(palindromeInt))
            {
                return palindromeInt;
            }
        }
        return 0;
    }

    public static bool CheckThreeDigitDivisorExists(int number)
    {
        for (int i = 999; i > 100; i--)
        {
            if (number % i == 0)
            {
                if (number / i <= 999)
                {
                    return true;
                }
            }
        }
        return false;
    }

    public static string ReverseString(string s)
    {
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        return new string(arr);
    }

Answer 6

I don't think, there is a real problem with your code. You just do not filter for the largest product, which is not necessarily your last output. Just add an additional check for the largest product, e.g. like this:

var x, y, product, max = 0;

for (x = 100; x <= 999; x++) {
    for (y = x; y <= 999; y++) {
        product = x * y;
        if (Palindromic(product)) {
          if( max < product ) { // this is new
            max = product;
            console.log(x + '*' + y + '=' + product);
          }
        }
    }
}

This returns

913*993=906609

as the largest result.