Documentation for Palindrome Number Solution

Problem Statement

Given an integer x, return true if x is a palindrome, and false otherwise. A number is considered a palindrome if it reads the same backward as forward.

Examples

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

2. Input: x = -121
   Output: false
   Explanation: -121 reads as 121- from left to right and is not the same backward.

Constraints

• The integer x can be negative, which automatically disqualifies it from being a palindrome.
• The solution must handle large integers without causing overflow.

Solution Overview

The solution involves reversing the digits of the integer and comparing the reversed number with the original number. If they are the same, the number is a palindrome.

Intuition Behind the Solution

1. Negative Numbers: Any negative number cannot be a palindrome because of the negative sign.
2. Reversing the Number: By reversing the digits of the number, we can easily check if the original number and the reversed number are the same.
3. Overflow Prevention: We need to ensure that reversing the number does not cause an overflow, which is handled by checking if the current reversed number exceeds INT_MAX / 10.

Step-by-Step Dry Run

Let's dry run the code with the input x = 121.

1. Initialization:

   • num = 121
   • ans = 0

2. Check for Negative:

   • Since 121 is not negative, we proceed.

3. While Loop:

   • First Iteration:
     • num = 121
     • Check if ans > INT_MAX / 10: 0 > INT_MAX / 10 (false)
     • Update ans: ans = 0 * 10 + (121 % 10) = 0 + 1 = 1
     • Update num: num = 121 / 10 = 12
   • Second Iteration:
     • num = 12
     • Check if ans > INT_MAX / 10: 1 > INT_MAX / 10 (false)
     • Update ans: ans = 1 * 10 + (12 % 10) = 10 + 2 = 12
     • Update num: num = 12 / 10 = 1
   • Third Iteration:
     • num = 1
     • Check if ans > INT_MAX / 10: 12 > INT_MAX / 10 (false)
     • Update ans: ans = 12 * 10 + (1 % 10) = 120 + 1 = 121
     • Update num: num = 1 / 10 = 0

4. Exit Loop:

   • The loop exits as num is now 0.

5. Final Comparison:

   • Check if ans == x: 121 == 121 (true)
   • Return true.

Code Explanation

class Solution {
public:
    bool isPalindrome(int x) {
        int num = x, ans = 0;

        // Check for negative numbers
        if (x < 0)
            return false;

        // Reverse the number
        while (num) {
            // Check for overflow
            if (ans > INT_MAX / 10)
                return false;

            ans = ans * 10 + (num % 10); // Append last digit
            num /= 10; // Remove last digit
        }

        // Compare reversed number with original
        return ans == x;
    }
};

Key Points

• Efficiency: The solution runs in O(log10(n)) time complexity, where n is the number of digits in the integer.
• Space Complexity: O(1) since we are using a constant amount of space.
• Edge Cases: The solution correctly handles negative numbers and potential overflow scenarios.

Conclusion

This solution effectively checks if a number is a palindrome by reversing its digits and comparing the result with the original number. The approach is efficient and straightforward, making it suitable for beginners to understand the concept of palindromes in integers.