Question 9

Palindrome Number Problem

Approach: Converting Half of The Numbers

This solution checks if an integer x is a palindrome by reversing half of the digits and comparing them.

Steps:

1. Handle Special Cases:

   • If x is negative, return false since negative numbers cannot be palindromes.
   • If x ends in 0 and is not 0 itself, return false because the first digit of a palindrome cannot be 0 (except for the number 0).

2. Reverse Half of the Number:

   • Initialize revertedNumber to 0.
   • Reverse the last half of the digits by continuously moving the last digit of x to revertedNumber until x is no longer greater than revertedNumber.

3. Check for Palindrome:

   • After the loop, x should either be equal to revertedNumber (for even-length palindromes) or revertedNumber / 10 (for odd-length palindromes, where the middle digit does not need to be compared).

4. Complexity

   • Time Complexity: O(log₁₀(n)), as the number of digits is reduced by half.
   • Space Complexity: O(1), using constant extra space.

class Solution {
    public boolean isPalindrome(int x) {
        // Special cases:
        // If x is negative, it is not a palindrome.
        // Similarly, if the last digit of x is 0, the first digit also needs to be 0
        // for it to be a palindrome. Only 0 meets this criterion.
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

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

        // If the number length is odd, we can remove the middle digit by dividing revertedNumber by 10.
        // For example, if the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123.
        // The middle digit does not affect the palindrome check (it is equal to itself), so we can remove it.
        return x == revertedNumber || x == revertedNumber / 10;
    }
}