Palindrome Number easy

Problem Statement

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. For example, 121 is a palindrome, while 123 is not.

Example 1:

Input: x = 121 Output: true

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.

Steps:

1. Handle Negative Numbers: Negative numbers are never palindromes because of the minus sign. Return false immediately if the input x is negative.

2. Reverse the Number: Reverse the integer x. We can do this efficiently without converting to a string.

3. Compare Original and Reversed: Compare the original number x with its reversed version. If they are equal, the number is a palindrome; otherwise, it's not.

Explanation:

The core idea is to reverse the integer and compare it to the original. Reversing an integer efficiently in Java involves repeatedly extracting the last digit using the modulo operator (%), building the reversed number, and removing the last digit from the original number using integer division (/).

Code:

class Solution {
    public boolean isPalindrome(int x) {
        // Handle negative numbers
        if (x < 0) {
            return false;
        }

        // Handle single-digit numbers
        if (x < 10) {
            return true;
        }

        int original = x;
        int reversed = 0;

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

        return original == reversed;
    }
}

Complexity:

• Time Complexity: O(log₁₀(n)), where n is the input integer. This is because the number of digits in an integer is proportional to the logarithm of the integer (base 10). The while loop iterates once for each digit.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. We only store a few integer variables.