# 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:

```text
121
```

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

But:

```text
-121
```

is not a palindrome, because reversing it gives:

```text
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

| Item | Meaning |
|---|---|
| Input | An integer `x` |
| Output | `true` if `x` is a palindrome, otherwise `false` |
| Constraint | `-2^31 <= x <= 2^31 - 1` |
| Follow-up | Solve without converting the integer to a string |

Example function shape:

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

## Examples

Example 1:

```text
x = 121
```

Output:

```text
true
```

Explanation:

```text
121
```

reads the same forward and backward.

Example 2:

```text
x = -121
```

Output:

```text
false
```

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

Example 3:

```text
x = 10
```

Output:

```text
false
```

Reading backward gives:

```text
01
```

which is not the same integer form as:

```text
10
```

## First Thought: Convert to String

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

```python
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:

```text
x = 1221
```

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

```text
x = 122, reversed_half = 1
x = 12,  reversed_half = 12
```

Now compare:

```text
x == reversed_half
12 == 12
```

So `1221` is a palindrome.

For an odd number of digits:

```text
x = 12321
```

After reversing half:

```text
x = 12, reversed_half = 123
```

The middle digit does not matter.

So we compare:

```text
x == reversed_half // 10
12 == 12
```

This is why the final condition has two cases:

```python
x == reversed_half or x == reversed_half // 10
```

## Early Rejections

Negative numbers cannot be palindromes:

```python
x < 0
```

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

For example:

```text
10
```

would need to read backward as:

```text
01
```

But integers do not keep leading zeros.

So we reject:

```python
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:

```python
reversed_half = reversed_half * 10 + x % 10
```

appends the last digit of `x` to the reversed half.

The operation:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(log10(x))` | We process half of the decimal digits |
| Space | `O(1)` | Only integer variables are stored |

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

## Implementation

```python
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:

```python
if x < 0:
    return False
```

Reject numbers like `10`, `100`, and `1230`:

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

Then reverse only half of the number:

```python
while x > reversed_half:
```

Move the last digit from `x` to `reversed_half`:

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

Finally compare the two halves:

```python
return x == reversed_half or x == reversed_half // 10
```

The first comparison handles even digit counts.

The second comparison handles odd digit counts.

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `121` | Basic odd-length palindrome |
| `-121` | Negative number |
| `10` | Ends with zero |
| `0` | Zero is a palindrome |
| `1221` | Even-length palindrome |
| `12321` | Odd-length palindrome |
| `1231` | Non-palindrome |
| `1001` | Internal zeros |
| `100` | Trailing zeros |