Palindrome

July 20, 2021

In this post, I discuss my experience of solving my very first problem on LeetCode.

The Problem

To write a program that can check if an integer is a palindrome or not. It was also provided that negative integers and integers ending with one or more zeroes would be deemed to be non-palindromes.

It was suggested that the program be written without converting the integer to a string (though this was not mandatory).

My Attempt

I solved this problem using a for-loop:

var isPalindrome = function (x) {
  if (x < 0) {
    return false;
  }
  let lastDigit = x % 10;
  if (lastDigit == 0) {
    if (x == lastDigit) {
      return true;
    }
    return false;
  }
  let reverse = 0;

  for (let i = x; i > 0; i = Math.floor(i / 10)) {
    reverse = reverse * 10 + (i % 10);
  }
  if (reverse == x) {
    return true;
  }
  return false;
};

Is there a better way to solve this problem?

Although my solution was accepted by LeetCode, I was curious if there was a more elegant solution that took a lesser run-time or required lesser memory to do the same task. So, I looked into some of the solutions posted by others on the discussion section of LeetCode.

Taking a cue from some of the solutions, I figured a better way to write the same program. I realised that the key is to run the loop only till the half-way point.

When x is an even number

Table the iteration of the loop where x is an even number

When x is an odd number

Table the iteration of the loop where x is an even number

Comparing x with reverse

After the loop is terminated, we should see if x == reverse || x == Math.Floor(reverse/10), to see if x is in fact a palindrome. [In the case of an odd number, reverse will always have an extra digit (i.e., the middle digit). Thus, while comparing the two, we should see if reverse without its last digit equals to x].

Putting everything together:

let reverse = 0;
while (x > reverse) {
  reverse = reverse * 10 + (x % 10);
  x = Math.floor(x / 10);
}
if (reverse == x || Math.floor(reverse / 10) == x) {
  return true;
}
return false;
};