Palindrome Number

Patrick Leaton
Published: March 6, 2021, 3:07 a.m.
Problem Description

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

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

 

Example 1:

Input: x = 121
Output: true

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.

Example 4:

Input: x = -101
Output: false

Constraints:

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

 

The description was taken from https://leetcode.com/problems/palindrome-number/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        result, input_int = 0, x
        while x != 0:
            result *= 10
            result += x%10
            x //= 10
        return input_int == result

Problem Explanation

If a number was a palindrome, then it would be the same going from left to right as it is going from right to left.  Meaning, its most significant digit to least significant digit ordering would be the same as its least significant digit to most significant digit ordering.

Knowing this, we can create a new number and iteratively place within it each least significant digit from the input number it using the modulo and division operators.  Once the new number has been created, we will compare it to the input number.  If they are the same, then the number is a palindrome.

First off, If the input integer is less than zero then we will return false because a negative number cannot be a palindrome due to the starting negative sign.

        if x < 0:
            return False

 

Let's initialize our result integer and save the input number for comparison later.

        result, input_int = 0, x

 

While x is greater than zero, in each iteration, we will multiply the result by ten to set a placeholder.

Then, we will add the last digit of x to the result through modulo x by ten, so that we isolate the least significant base-ten digit.

We will then divide x by ten to chop off that least significant digit.

        while x != 0:
            result *= 10
            result += x%10
            x //= 10

 

Once we are out of the loop and have added each digit from the input to the result in a backward fashion, we will see if these two numbers are the same.

        return input_int == result