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, so we can immediately return false if the input x is negative.

2. Reverse the Number: We need to reverse the integer to compare it with the original. We can do this using a while loop and repeatedly extract the last digit using the modulo operator (%).

3. Compare Original and Reversed: After reversing, compare the original number with the reversed number. If they are equal, it's a palindrome; otherwise, it's not.

Explanation

The key idea is to efficiently reverse the integer without converting it to a string. Using modulo and integer division, we can extract digits one by one and build the reversed number. This avoids the overhead of string manipulation, making the solution more efficient.

Code

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

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

        int original = x;
        int reversed = 0;

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

        // Compare original and reversed
        return original == reversed;
    }
}

Complexity

• Time Complexity: O(log10(n)), where n is the input integer. The number of iterations in the while loop is proportional to the number of digits in the integer, which is logarithmic with respect to the value of the integer.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. We only use a few integer variables to store the original number, reversed number, and temporary values.