003.md

9. Palindrome Number

Difficulty: 🟢 Easy

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

Examples:

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

Follow up:

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

Solutions

O(n) solution

Python3

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False

        number, reverse, counter = x, 0, 0
        while True:
            reverse = reverse * 10 + number % 10
            number = number // 10
            counter += 1
            if not number:
                break
        return x == reverse

The given solution solves the problem by first checking if x is negative. If x is negative, it immediately returns False since a negative number cannot be a palindrome. If x is non-negative, the solution uses a while loop to reverse the digits of x and stores the reversed number in the variable reverse. Finally, it compares x with reverse and returns True if they are equal, indicating that x is a palindrome, or False otherwise.

The algorithm follows these steps:

1. Check if x is negative. If it is, return False immediately since negative numbers cannot be palindromes.
2. Initialize variables number, reverse, and counter to x, 0, and 0, respectively.
3. Enter a while loop that continues until the loop condition is explicitly broken.
4. Inside the while loop, calculate the next digit of the reversed number by using the expression reverse = reverse * 10 + number % 10, where number % 10 gives the last digit of number and reverse * 10 shifts the existing digits to the left.
5. Divide number by 10 using the floor division operator number //= 10 to remove the last digit.
6. Increment the counter by 1 to keep track of the number of digits processed.
7. Check if number is zero. If it is, break the while loop.
8. Repeat steps 4-7 until the loop condition is explicitly broken.
9. Compare x with reverse. If they are equal, return True to indicate that x is a palindrome; otherwise, return False.

Complexity Analysis

The time complexity of the algorithm is O(D), where D is the number of digits in the input number x. This is because the algorithm iterates through each digit of x in the while loop, performing constant-time operations.

The space complexity of the algorithm is O(1) because it uses a constant amount of additional space to store the number, reverse, and counter variables.

Summary

The given solution determines whether the given integer x is a palindrome or not. It first checks if x is negative, and if it is, it immediately returns False. If x is non-negative, the algorithm reverses the digits of x and compares it with the original number to determine if x is a palindrome. The algorithm has a time complexity of O(D) and a space complexity of O(1), where D is the number of digits in x.

User suggested solutions in other languages

TypeScript

function isPalindrome(x: number): boolean {
  if (x < 0) return false;

  let originalNumber = x;
  let reversedNumber = 0;

  while (x > 0) {
    let lastDigit = x % 10;
    reversedNumber = reversedNumber * 10 + lastDigit;
    x = Math.floor(x / 10);
  }

  return originalNumber === reversedNumber;
}

Php

class Solution {
    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
       if ($x < 0 || ($x % 10 == 0 && $x != 0)) {
            return false;
        }

        $reverse = 0;
        $number = $x;
        
        while ($number > $reverse) {
            $reverse = $reverse * 10 + $number % 10;
            $number = (int)($number / 10);
        }
        
        return $number == $reverse || $number == (int)($reverse / 10);
        
    }
}

NB: If you want to get community points please suggest solutions in other languages as merge requests.