Palindrome Number

---

Palindrome Number: Given an integer x, return true if x is a palindrome, and false otherwise.

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:

• -2^31 <= x <= 2^31 - 1

---

Try this Problem on your own or check similar problems:

1. Palindrome Linked List
2. Find Palindrome With Fixed Length
3. Strictly Palindromic Number

Solution:

Java

public boolean isPalindrome(int x) {
  if(x < 0) return false;
  int numberOfDigits = (int) Math.floor(Math.log10(x));
  int power = (int) Math.pow(10,numberOfDigits);
  while(x > 0){
      if(x / power != x % 10) return false;

      x -= (x / power) * power;
      x -= (x % 10);
      x /= 10;
      power /= 100;
  }
  return true;
}

JavaScript

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
  if (x < 0) return false;
  let numberOfDigits = Math.floor(Math.log10(x));
  let power = Math.pow(10, numberOfDigits);
  while (x > 0) {
    if (Math.floor(x / power) !== x % 10) return false;

    x -= Math.floor(x / power) * power;
    x -= x % 10;
    x /= 10;
    power /= 100;
  }
  return true;
};

Python

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        if x == 0:
            return True
        numberOfDigits = int(math.log10(x))
        power = 10 ** numberOfDigits
        while x > 0:
            if x // power != x % 10:
                return False

            x -= (x // power) * power
            x -= x % 10
            x //= 10
            power //= 100
        return True

C++

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        if (x == 0) return true;
        int numberOfDigits = (int)std::floor(std::log10(x));
        int power = (int)std::pow(10, numberOfDigits);
        while (x > 0) {
            if (x / power != x % 10) return false;

            x -= (x / power) * power;
            x -= (x % 10);
            x /= 10;
            power /= 100;
        }
        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(logx)
• Space Complexity: O(1)

---

Explanation:

We could create a string from the input and then use the Valid Palindrome, but this would requires us to spend additional space leading to linear space complexity O(n) where n is the number of digits of our input, you could make case that space complexity is O(log10(x) + 1) (formula we can use to get count of digits for any number). We can however use the input number and do operations on it each time checking if the current digits on each end are the same, to do that we need a way to get first and last digit of number and then move to the middle from both sides. We can get the first digit by calculating the number of digits number is represented with (Math.log10(x)) and then using that information to get the power (e.g. for x = 9889 we will have power 1000) which makes it easy to get the first digit, to get the last digit we just take the remainder by division with 10. Now we need to move to the middle from both side, so we first subtract (x / power) * power (e.g. x = 9889 we will have 9889 - 9 * 1000 = 889), then we subtract the remainder (last digit) 889 - 889 % 10 = 880 and finally we divide by 10 to remove the last 0. For the next iteration since we lost two digits, we have to divide power by 100. If we iterated all number's digits and didn't get false we can return true since the number is a palindrome. Time complexity is logarithmic, since we cover all number digits log10(x) + 1. Also note that negative number can never be palindrome since it has - at the beginning.