9. Palindrome Number

 

Palindrome Number

Problem Description

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

• For example, 121 is a palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false

Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false

Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

 

Constraints:

• -231 <= x <= 231 - 1

 

Follow up: Could you solve it without converting the integer to a string?

String-based reversal

In this method, we will convert the number to a string, reverse it and check if the initial number is equal to the new one. We will use some built-in JavaScript methods.

Idea:

• convert to string
• create a character array
• reverse it
• join it back to a string
• check for equality
• Let's see a simple implementation of the above logic.

Let's Code It!

var isPalindrome = function(x) {
  return x == x.toString().split('').reverse().join('');
};

Notice the == as opposed to === because we want to check if both sides are equal regardless of their type. In this case, X is a number while the computed value is a string.

• Some of the methods chained are
• toString() to convert the number to a string
• split() to convert the string to an array of characters
• reverse() to reverse the array
• join() to join the array back to a string

This will also solve the problem with the sign of the number. When we convert the number to a string, the minus sign becomes the part of the string and on reversal goes to the end. For example, -123 becomes 321-.

This is all we need to solve the problem, once we submit it, these are the stats.

Time complexity

We use a bunch of methods, all with linear time complexity, but they are chained as opposed to nested, so the runtime will be dependent on the number of digits in the input. We can say O(len X)

Space complexity

We have a number as input, not using any other temporary variable to store the result, so space complexity is constant, O(1)

Number based reversal

In this method, we will pick the digits of the number one by one and reverse the number without converting it to string

Idea:

• check if the number is less than zero
• if the number is less than zero, return false
• initialize a variable temp with X ( because we lose the initial value of X in the logic)
• initialize the reverse variable with 0
• loop over the number until it's less than or equal to zero (at one point it will be)
• now, multiply the reversed variable by 10 and add the last digit of the number to it
• remove the last digit of X
• when the loop ends, we will have our reversed number
• if the reversed number is equal to temp ( initial number ), return true
• else, false

Let's Code It!

var isPalindrome = function(x) {
  const isNegative = x< 0 ? true : false;
    
  if (isNegative){
      return false;
  }
    
  const temp = x;
  let reversed = 0;
    
  while(x>0){
      reversed = (reversed * 10) + (x%10);
      x = parseInt(x/10);
  }
    
  return reversed == temp;
};

So as discussed above, first, we determine if the number is negative, and return false. 
Next, the logic is pretty straightforward, check if the reversed number is equal to temp, and return the result.

Time and Space complexity

Unfortunately, we didn't improve the time complexity. It's O(len X) ( notice the loop runs len X times). The same goes for space, O(1).

Two pointer method

In this approach, we will take care of some of the simple cases before writing out the logic. Once those are taken care of, we will follow the two-pointer method to check if the number is a palindrome.

The idea is, we will take one digit from the start, and another from the last. Check if both are equal if not, the number is not a palindrome.

var isPalindrome = function (x) {

  if (x < 0) {
    return false;
  }

  if (x < 10) {
    return true;
  }

  if (x % 10 === 0 && x !== 0) {
    return false;
  }

  const str = String(x);
  let i = 0, j = str.length - 1;

  while (i < j) {
    if (str[i] !== str[j]) {
      return false;
    }

    i++;
    j--;
  }

  return true;
};

First, we took care of the following cases

• if X is negative ( not a palindrome )
• if X is less than ten ( always a palindrome )
• if X has 0 at its last digit and X is not 0 itself ( not a palindrome ) e.g. 10, 130 whose reverse will be 01, 031 respectively

Next, the logic is straightforward

• convert the number to a string
• take two pointers, at the start and end of the string
• if the digits at both pointers are different, it's not a palindrome
• we increment starting pointer and decrement the end pointer iteratively
• if the loop exits, then it was a palindrome
• This is all we need to solve the problem, once we submit it, these are the stats.

Time complexity

We see a bit of improvement in run time. We are running logic only for positive numbers greater than 9. Also, in the loop, we are taking two steps instead of 1. However, asymptotically the running time complexity is still O(len x) 

Space complexity

We have a number as input, using a couple of more temporary variables, so space complexity is constant, O(1)

Conclusion

That’s all folks! In this post, we solved LeetCode problem #9 Palindrome Number

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!