LeetCode 9 - Palindrome Number

LeetCode Problem 9

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine whether a given integer reads the same forward and backward. Such numbers are called palindromes. For example, the number 121 is a palindrome because reversing its digits still produces 121. On the other hand, 123 is not a palindrome because reversing it produces 321.

The input consists of a single integer x. The output should be a boolean value:

• Return true if the integer is a palindrome.
• Return false otherwise.

One important detail is that negative numbers are never palindromes. A number like -121 is not considered a palindrome because reversing its characters produces 121-, which is not the same sequence.

The constraints specify that the value fits within the standard 32-bit signed integer range:

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

This tells us that the number of digits is small, at most 10 digits. Even though the input size is small, the follow up explicitly asks whether we can solve the problem without converting the integer into a string. That means the intended solution is based on mathematical digit manipulation rather than string operations.

Several edge cases are important:

• Negative numbers should immediately return false.
• Numbers ending in 0 are usually not palindromes unless the number itself is 0.
• Single digit numbers are always palindromes.
• Very large values near the integer limit should still work correctly without overflow issues.

Understanding these cases upfront helps avoid subtle bugs later in the implementation.

Approaches

Brute Force Approach

The most straightforward solution is to convert the integer into a string and then compare the string with its reverse.

For example:

• Convert 121 into "121"
• Reverse it to "121"
• Compare the two strings

If they are equal, the number is a palindrome.

This approach is easy to implement and easy to understand. Reversing a string is efficient, and the maximum number of digits is small. However, it does not satisfy the follow up requirement because it relies on string conversion rather than pure arithmetic operations.

Optimal Approach

The key observation is that we do not need to reverse the entire number. We only need to reverse half of it.

Suppose we process the digits from right to left and gradually build a reversed number:

x = 1221
reversedHalf = 0

Step 1:
digit = 1
reversedHalf = 1
x = 122

Step 2:
digit = 2
reversedHalf = 12
x = 12

At this point, x and reversedHalf are equal, which means the number is a palindrome.

This approach has several advantages:

• No string conversion is needed.
• Only half the digits are processed.
• Overflow is avoided because the reversed value never grows beyond half the original number.

There is one extra detail for odd length numbers. For example:

12321

The middle digit does not matter for palindrome checking. After processing half the digits:

x = 12
reversedHalf = 123

Removing the middle digit with reversedHalf // 10 gives:

123 // 10 = 12

Now the two halves match.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Converts integer to string and reverses it
Optimal	O(d)	O(1)	Reverses only half the digits mathematically

Here, d represents the number of digits in the integer.

Algorithm Walkthrough

1. First, handle invalid cases early.

If the number is negative, return false immediately because negative numbers cannot be palindromes.

Also, if the number ends in 0 but is not exactly 0, return false. A palindrome cannot start with 0, so such numbers are impossible. 2. Initialize a variable called reversed_half to 0.

This variable will store the reversed digits taken from the right side of the number. 3. Repeatedly extract digits from the original number.

In each iteration:

• Take the last digit using x % 10
• Append it to reversed_half
• Remove the last digit from x using integer division

4. Continue the loop until reversed_half becomes greater than or equal to x.

This condition means we have processed half the digits. 5. After the loop, compare the two halves.

There are two possibilities:

• Even number of digits:

x == reversed_half

• Odd number of digits:

The middle digit should be ignored:

x == reversed_half // 10

6. Return the comparison result.

Why it works

The algorithm maintains the invariant that reversed_half always contains the reverse of the digits removed from the right side of x. By stopping once the reversed half becomes greater than or equal to the remaining half, we ensure that exactly half the digits have been processed. For even length numbers, the two halves should match exactly. For odd length numbers, the middle digit is irrelevant and can be removed with integer division by 10.

Python Solution

class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Negative numbers are not palindromes
        # Numbers ending in 0 are not palindromes unless the number is 0
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        reversed_half = 0

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

        # For even length numbers:
        # x == reversed_half
        #
        # For odd length numbers:
        # x == reversed_half // 10
        return x == reversed_half or x == reversed_half // 10

The implementation begins by handling the invalid cases immediately. Negative numbers and numbers ending in zero are rejected because they cannot form valid palindromes.

The variable reversed_half is used to store the reversed digits from the right side of the original number. Inside the loop, the last digit is extracted using modulo arithmetic and appended to the reversed value.

The loop stops once reversed_half becomes greater than or equal to x. At that point, half the digits have been processed.

Finally, the code checks both the even length and odd length scenarios. For odd length numbers, integer division by 10 removes the center digit before comparison.

Go Solution

func isPalindrome(x int) bool {
    // Negative numbers are not palindromes
    // Numbers ending in 0 are not palindromes unless the number is 0
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    reversedHalf := 0

    for x > reversedHalf {
        digit := x % 10
        reversedHalf = reversedHalf*10 + digit
        x /= 10
    }

    // Even length:
    // x == reversedHalf
    //
    // Odd length:
    // x == reversedHalf/10
    return x == reversedHalf || x == reversedHalf/10
}

The Go implementation follows exactly the same logic as the Python version. One small language difference is that integer division in Go uses / rather than //. Since all values are integers, the result is automatically truncated toward zero.

No special overflow handling is required because only half of the number is reversed, which keeps the intermediate value safely within range.

Worked Examples

Example 1

Input: x = 121

Initial state:

Step	x	reversed_half
Start	121	0

First iteration:

• Extract digit: 121 % 10 = 1
• Update reversed half: 0 * 10 + 1 = 1
• Remove digit from x: 121 // 10 = 12

Step	x	reversed_half
After 1st iteration	12	1

Second iteration:

• Extract digit: 12 % 10 = 2
• Update reversed half: 1 * 10 + 2 = 12
• Remove digit from x: 12 // 10 = 1

Step	x	reversed_half
After 2nd iteration	1	12

The loop stops because x <= reversed_half.

Final check:

x == reversed_half // 10
1 == 12 // 10
1 == 1

Result:

true

Example 2

Input: x = -121

The number is negative, so the algorithm immediately returns:

false

Example 3

Input: x = 10

The number ends in 0 but is not equal to 0.

The algorithm immediately returns:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Processes roughly half the digits
Space	O(1)	Uses only a few integer variables

The algorithm processes each digit at most once. Since an integer with d digits requires d digit operations, the runtime is linear in the number of digits. The space usage remains constant because no additional data structures are allocated.

Test Cases

solution = Solution()

assert solution.isPalindrome(121) == True      # Standard palindrome
assert solution.isPalindrome(-121) == False    # Negative number
assert solution.isPalindrome(10) == False      # Ends with zero
assert solution.isPalindrome(0) == True        # Zero is a palindrome
assert solution.isPalindrome(7) == True        # Single digit
assert solution.isPalindrome(11) == True       # Two digit palindrome
assert solution.isPalindrome(12) == False      # Two digit non-palindrome
assert solution.isPalindrome(1221) == True     # Even length palindrome
assert solution.isPalindrome(12321) == True    # Odd length palindrome
assert solution.isPalindrome(123421) == False  # Similar but not palindrome
assert solution.isPalindrome(1001) == True     # Internal zeros
assert solution.isPalindrome(100) == False     # Trailing zeros
assert solution.isPalindrome(2147447412) == True   # Large palindrome
assert solution.isPalindrome(2147483647) == False  # Max 32-bit integer

Test	Why
121	Basic palindrome case
-121	Verifies negative numbers are rejected
10	Verifies trailing zero rule
0	Ensures zero is treated correctly
7	Single digit numbers should work
11	Small even length palindrome
12	Small non-palindrome
1221	Even number of digits
12321	Odd number of digits
123421	Similar structure but invalid
1001	Handles zeros inside the number
100	Invalid because of trailing zeros
2147447412	Large valid palindrome
2147483647	Large invalid number

Edge Cases

Negative Numbers

Negative integers are a common source of mistakes. A naive implementation might reverse the digits and compare absolute values, incorrectly treating -121 as a palindrome. However, the minus sign changes the sequence, so the number is not symmetric. The implementation handles this immediately with:

if x < 0:
    return False

This guarantees that all negative inputs are rejected before any further processing.

Numbers Ending in Zero

Numbers like 10, 100, and 120 can cause subtle bugs. Reversing 10 produces 01, which is effectively 1, not 10. A palindrome cannot begin with zero, so any nonzero number ending in zero must be invalid.

The implementation explicitly checks:

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

This correctly allows 0 itself while rejecting all other trailing zero cases.

Odd Length Palindromes

Odd length palindromes contain a middle digit that does not need a matching counterpart. For example:

12321

The center digit 3 can be ignored. A common bug is comparing the two halves directly without removing the middle digit.

The implementation handles this by comparing:

x == reversed_half // 10

Dividing by 10 removes the extra middle digit, allowing odd length palindromes to be recognized correctly.