LeetCode 9: Palindrome Number

Problem Restatement

We are given an integer x.

Return true if x is a palindrome integer.

Return false otherwise.

A palindrome reads the same forward and backward. For example:

121

is a palindrome because it reads the same from both directions.

But:

-121

is not a palindrome, because reversing it gives:

121-

The follow-up asks whether we can solve the problem without converting the integer to a string. The input range is -2^31 <= x <= 2^31 - 1.

Input and Output

Example function shape:

def isPalindrome(x: int) -> bool:
    ...

Examples

Example 1:

x = 121

Output:

true

Explanation:

121

reads the same forward and backward.

Example 2:

x = -121

Output:

false

A negative sign appears only on the left side. So a negative number cannot read the same backward.

Example 3:

x = 10

Output:

false

Reading backward gives:

01

which is not the same integer form as:

10

First Thought: Convert to String

The simplest solution is to convert the number to a string and compare it with its reverse.

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        return s == s[::-1]

This works for the basic problem.

But the follow-up asks for a solution without string conversion, so we should solve it with arithmetic.

Key Insight

We can reverse only the second half of the number.

For example:

x = 1221

Take digits from the right side and build a reversed half:

x = 122, reversed_half = 1
x = 12,  reversed_half = 12

Now compare:

x == reversed_half
12 == 12

So 1221 is a palindrome.

For an odd number of digits:

x = 12321

After reversing half:

x = 12, reversed_half = 123

The middle digit does not matter.

So we compare:

x == reversed_half // 10
12 == 12

This is why the final condition has two cases:

x == reversed_half or x == reversed_half // 10

Early Rejections

Negative numbers cannot be palindromes:

x < 0

Numbers ending in 0 also cannot be palindromes unless the number is exactly 0.

For example:

10

would need to read backward as:

01

But integers do not keep leading zeros.

So we reject:

x != 0 and x % 10 == 0

Algorithm

1. If x < 0, return False.
2. If x ends in 0 and x != 0, return False.
3. Set reversed_half = 0.
4. While x > reversed_half:
   • take the last digit of x
   • append it to reversed_half
   • remove the last digit from x
5. Return whether:
   • x == reversed_half, for even digit count
   • or x == reversed_half // 10, for odd digit count

Correctness

At each loop step, we move one digit from the end of x into reversed_half.

The operation:

reversed_half = reversed_half * 10 + x % 10

appends the last digit of x to the reversed half.

The operation:

x //= 10

removes that digit from x.

So after k steps:

• x contains the original number without its last k digits
• reversed_half contains those k removed digits in reversed order

The loop stops when reversed_half has at least as many digits as x.

For even digit counts, both halves should be equal.

For odd digit counts, reversed_half has one extra middle digit, so we drop it with integer division by 10.

Therefore the algorithm returns True exactly when the original integer reads the same forward and backward.

Complexity

For the given 32-bit range, this is bounded by a small constant.

Implementation

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

        if x != 0 and x % 10 == 0:
            return False

        reversed_half = 0

        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10

        return x == reversed_half or x == reversed_half // 10

Code Explanation

Reject negative numbers:

if x < 0:
    return False

Reject numbers like 10, 100, and 1230:

if x != 0 and x % 10 == 0:
    return False

Then reverse only half of the number:

while x > reversed_half:

Move the last digit from x to reversed_half:

reversed_half = reversed_half * 10 + x % 10
x //= 10

Finally compare the two halves:

return x == reversed_half or x == reversed_half // 10

The first comparison handles even digit counts.

The second comparison handles odd digit counts.

Testing

def run_tests():
    s = Solution()

    assert s.isPalindrome(121) is True
    assert s.isPalindrome(-121) is False
    assert s.isPalindrome(10) is False
    assert s.isPalindrome(0) is True
    assert s.isPalindrome(1221) is True
    assert s.isPalindrome(12321) is True
    assert s.isPalindrome(1231) is False
    assert s.isPalindrome(1001) is True
    assert s.isPalindrome(100) is False

    print("all tests passed")

run_tests()