Domain 1EasyCORE

Palindrome Number

The problem asks us to determine if a given integer `x` is a palindrome. An integer is considered a palindrome if it reads the same backward as forward. The input is a single integer, and the output should be a boolean value (`true` or `false`).

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

9. Palindrome Number

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 50.0%


Problem Breakdown

The problem asks us to determine if a given integer x is a palindrome. An integer is considered a palindrome if it reads the same backward as forward. The input is a single integer, and the output should be a boolean value (true or false).

Inputs:

  • A single integer x.

Outputs:

  • A boolean indicating whether x is a palindrome.

Implicit Constraints/Edge Cases:

  1. Negative numbers are not palindromes because of the negative sign.
  2. Numbers ending in zero (except 0 itself) cannot be palindromes since they would have a leading zero when reversed.
  3. The integer range is constrained by -2^31 to 2^31 - 1.

Intuition

A brute-force approach would involve converting the integer to a string and then checking if the string reads the same backward as forward. This method is straightforward but has a time complexity of O(n) due to the string reversal operation, where n is the number of digits in the integer.

However, we can improve this by avoiding string conversion. The key insight is to reverse only half of the number and compare it with the other half. This reduces the space complexity to O(1).

Approach

To solve this problem without converting the integer to a string, we can follow these steps:

  1. Handle Negative Numbers: If x is negative, return false immediately since negative numbers cannot be palindromes.
  2. Reverse Half of the Number:
    • Initialize two variables: reversed_half = 0 and original = x.
    • While x > reversed_half, extract the last digit of x using x % 10 and add it to reversed_half after shifting its digits one place to the left (reversed_half * 10 + x % 10).
    • Remove the last digit from x by performing integer division (x //= 10).
  3. Compare the Halves:
    • If the number of digits in original is odd, ignore the middle digit by comparing reversed_half // 10 with x.
    • Otherwise, compare reversed_half with x.

Complexity Analysis

  • Time Complexity: O(log n), where n is the number of digits in the integer. This is because we are processing each digit of the number once.
  • Space Complexity: O(1). We are using a constant amount of extra space regardless of the input size.

Solution

def isPalindrome(x: int) -> bool:
    # Negative numbers cannot be palindromes
    if x < 0:
        return False
    
    reversed_half = 0
    original = x
    
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # If the number of digits is odd, ignore the middle digit
    return x == reversed_half or original // 10 == reversed_half

Edge Cases Handled

  • Negative Numbers: The function returns false immediately for negative numbers.
  • Numbers Ending in Zero (except 0 itself): These are handled by the condition where x > reversed_half, ensuring that only valid palindromes are considered.
  • Single-digit Numbers: Single-digit numbers are inherently palindromes and will return true.
  • Zero: The function correctly identifies zero as a palindrome.