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.

Steps

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

2. Reverse the Number: We'll reverse the number using integer division and modulo operations.

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

Explanation

The core idea is to efficiently reverse the integer and compare it to the original. We avoid converting the number to a string because string manipulation can be less efficient than direct integer operations.

The modulo operator (%) gives us the last digit, and integer division (/) removes the last digit. We build the reversed number digit by digit.

Code

class Solution {
public:
    bool isPalindrome(int x) {
        // Negative numbers are not palindromes
        if (x < 0) {
            return false;
        }

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

        int reversed = 0;
        int original = x;

        while (x > 0) {
            reversed = reversed * 10 + x % 10;  // Build the reversed number
            x /= 10;                         // Remove the last digit from the original
        }

        return original == reversed;
    }
};

Complexity

• Time Complexity: O(log10(x)) - The while loop iterates roughly the number of digits in x. The number of digits is logarithmic with respect to the value of x.

• Space Complexity: O(1) - We use only a few integer variables; the space used is constant regardless of the input size.