Palindrome Number

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left.

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.

Constraints:

• -231 <= x <= 231 - 1

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

Approach: Reverse Half of the Number (No String Conversion)

Algorithm

1. Negative numbers are never palindromes (the - sign breaks symmetry)
2. Numbers ending in 0 are not palindromes unless they are 0 itself
3. Repeatedly move the last digit of x onto a reversed half
4. Stop when the reversed half reaches or exceeds the remaining half
5. Compare: x == reversed (even length) or x == reversed / 10 (odd length)

Time & Space Complexity

• Time Complexity: O(log10 n) - processes roughly half the digits
• Space Complexity: O(1) - constant extra space

Java Implementation

public class PalindromeNumber {

    /**
     * Determine whether x is a palindrome.
     * @param x Input integer
     * @return true if x is a palindrome
     */
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversed = 0;
        while (x > reversed) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }

        return x == reversed || x == reversed / 10;
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: x = 121");
        System.out.println("Output: " + isPalindrome(121)); // Expected: true

        System.out.println("Input: x = -121");
        System.out.println("Output: " + isPalindrome(-121)); // Expected: false

        System.out.println("Input: x = 10");
        System.out.println("Output: " + isPalindrome(10)); // Expected: false
    }
}

Example Walkthrough

For x = 121:

1. x=121, reversed=0. Loop: reversed=1, x=12
2. x=12 > reversed=1: reversed=12, x=1
3. Loop ends (1 > 12 is false). Compare x=1 with reversed/10=1 -> true

For x = 1221:

1. x=1221, reversed=0: reversed=1, x=122
2. reversed=12, x=12
3. Loop ends. Compare x=12 with reversed=12 -> true

Key Points

1. Negative Numbers Fail Fast: A negative sign makes symmetry impossible
2. Trailing Zero Check: Except for 0, numbers ending in 0 can never be palindromes
3. Half Reversal: Only half the digits need reversing, avoiding overflow
4. Odd Length: The middle digit is dropped by comparing with reversed / 10
5. No String Conversion: Meets the follow-up requirement