Optimal verification if a number is Palindrom in JS

Question

I have a problem I am sitting on for the past few days.

I want to write an optimal (in JS) program for verifying if a number is a Palindrome.

My current approach:

function isPalidrom2(pali){
//MOST time consuming call - I am splitting the digit into char array. 
  var digits = (""+pali).split("");
//To get the length of it. 
  var size = digits.length;
  var isPali = true;
  for(var i = 0; i<Math.floor(size/2); i++){
    //I am comparing digits (first vs last, second vs last-1, etc.) one by one, if ANY of the pars is not correct I am breaking the loop. 
    if(parseInt(digits[i]) != parseInt(digits[size-i-1])){
      isPali = false;
      break;
    }
  }
  return isPali;
}

It's not optimal. The biggest amount of time I am waisting is the change from INT to STRING.

And I am out of ideas - I tried to understand the BIT operators but I can't. - I tried to google and look for alternative approaches - but I can't find anything. - I tried to play with different algorithms - but this one is the fastest I was able to apply.

So in short - my question is: "how can I make it faster?"

EDIT:

So the task I want to solve:

Find all of the prime numbers within the range of all five digit numbers. Among all of the multiplies (i*j) they are between them, find the most significant palindrome.

My current approach:

function isPrime(number){
  var prime = true;
  var i
  for(i = 2; i<= number/2; i++){
if((number%i)==0){
  prime = false;
  break;
}
  }
  return prime;
}

function get5DigitPrimeNr(){
  var a5DigitsPrime = [];
  var i;
  for(i = 10000; i<100000; i++){
if(isPrime(i)){
  a5DigitsPrime.push(i)
}
  }
  return a5DigitsPrime;
}

function isPalidrom(pali){
  var digits = (""+pali).split("");
  //we check if first and last are the same - if true, we can progress
  size = digits.length;
  return
(digits[0]==digits[size-1]) &&
(parseInt(digits.slice(1, Math.floor(size/2)).join("")) ==
  parseInt(digits.reverse().slice(1, Math.floor(size/2)).join("")))
}

function isPalidrom2_48s(str) {
  var str = str.toString();
  const lower = str.substr(0, Math.floor(str.length / 2));
  const upper = str.substr(Math.ceil(str.length / 2));
  return lower.split("").reverse().join("") === upper;
}

function isPalidrom_22s(pali){
  var digits = (""+pali).split("");
  var size = digits.length;
  for(var i = 0; i<Math.floor(size/2); i++){
//console.log("I am comparing: "+i+", and "+(size-i-1)+" elements in array")
//console.log("I am comparing digit: "+digits[i]+", and "+digits[(size-i-1)]+"")
if(digits[i] !== digits[size-i-1]){
  //console.log('nie sa rowne, koniec')
  return false;
}
  }
  return true;
}

function isPalidrom2_80s(pali){
  return parseInt(pali) == parseInt((""+pali).split("").reverse().join(""))
}

function runme(){
  var prime5digits = get5DigitPrimeNr();
  var size = prime5digits.length;
  var max = 0;
  var message = "";
  for(var i = 0; i<size; i++){
for(var j = 0; j<size; j++){
  var nr = prime5digits[i]*prime5digits[j];
  if(nr>max && isPalidrom2(nr)){
    max = nr;
    message = 'biggest palidrome nr: '+nr+', made from numbers: '+prime5digits[i]+' x '+prime5digits[j];
  }
}
  }
  console.log(message)
}

function timeMe(){
  var t0 = performance.now();
  runme();
  var t1 = performance.now();
  console.log("Function took " + millisToMinutesAndSeconds(t1 - t0) + " s to find the perfect palindrom.")
}

//helper functons:

function millisToMinutesAndSeconds(millis) {
  var minutes = Math.floor(millis / 60000);
  var seconds = ((millis % 60000) / 1000).toFixed(0);
  return minutes + ":" + (seconds < 10 ? '0' : '') + seconds;
}

Answer 1

Code :

There are multiple methods that you can use (dunno if they are optimal) :

Palindrom = _ => (_=''+_) === [..._].sort(_=>1).join``

Some more :

let isPalindrome = __ => (_=(__=__+'').length)==0||_==1?!0:__[0]==__.slice(-1)?isPalindrome(__.slice(1,-1)):!1

let isPalindrome = (s,i) => (i=i||0)<0||i>=(s=''+s).length>>1||s[i]==s[s.length-1-i]&&isPalindrome(s,++i);

let isPalindrome = (str) => {
  var len = ~~((str=str+'').length / 2);
  for (var i = 0; i < len; i++)
    if (str[i] !== str[str.length - i - 1])
      return false;
  return true;
}

Updated now takes numbers as input

Answer 2

If you're trying to speed things up, you could shave a few more seconds off by optimising your isPrime(n) function.

• You don't need to check every factor, only the prime factors less than sqrt(n)
• If you check every number from 2 to 99999 in ascending order, you can store the results as you go, so you don't need to keep re-calculating the list of previous primes

Something like this:

var savedPrimes = [2]

function isPrime(n){
    // call this method with increasing values of n (starting at 2), saving primes as we go,
    // so we can safely assume that savedPrimes contains all primes less than n
    for(var i=0; i<savedPrimes.length; i++)
    {
        var f = savedPrimes[i];
        if ((n % f) == 0)
            return false; // found a factor
        if (f*f>=n)
            break; // stop checking after f >= sqrt(n)
    }
    // no prime factors - we found a new prime
    savedPrimes.push(n);
    return true;
}


function get5DigitPrimeNr(){
    var a5DigitsPrime = [];
    var i;

    // first find all the primes less than 10000
    for(i = 3; i<10000; i++){
        isPrime(i);
    }

    // now find (and keep) the rest of the primes up to 99999
    for(i = 10000; i<100000; i++){
        if(isPrime(i)){
            a5DigitsPrime.push(i)
        }
    }
    return a5DigitsPrime;
}

EDIT - when I run your code with this method, I get a time of 10 sec

Answer 3

To keep the spirit of you code, you could exit the loop with return instead of break and use the string directly without converting to an array. Strings have, as arrays, the possibility of an access single character with an index.

function isPalidrom2(value) {
    var digits = value.toString(),
        length = digits.length,
        i, l;

    for (i = 0, l = length >> 1; i < l; i++) {
        if (digits[i] !== digits[length - i - 1]) {
            return false;
       }
    }
    return true;
}

console.log(isPalidrom2(1));
console.log(isPalidrom2(12));
console.log(isPalidrom2(1221));
console.log(isPalidrom2(123));

Answer 4

The fastest is probably to rely on javascripts native methods:

 function isPalindrome(str) {
   const lower = str.substr(0, Math.floor(str.length / 2));
   const upper = str.substr(Math.ceil(str.length / 2));

   return lower.split("").reverse().join("") === upper;
}

Or leave away all unneccessary conversions from your code:

function isPlaindrome(str) {
  const half = str.length / 2;
  for(var i = 0; i < half; i++)
    if(str[i] !== str[str.length - i - 1])
       return false;
  return true;
}