9. Palindrome Number | LeetCode in C#

Intuition

A number is a palindrome if it reads the same forwards and backwards. The first thought might be to convert the number into a string and check if it matches its reverse. However, the challenge is to solve this without converting the integer to a string, which calls for a numerical approach.

Approach

To determine if an integer is a palindrome without using string conversion, we reverse the integer by repeatedly extracting its last digit and appending it to a new reversed number. Here's how:

1. Negative Numbers: Start by handling negative numbers. Any negative number cannot be a palindrome since the negative sign only appears on one side.
2. Reverse Integer: Initialize reverseNumber to zero and a copy of the input x called y. While y is greater than zero, repeatedly:
   • Extract the last digit (y % 10) from y and append it to reverseNumber by multiplying reverseNumber by 10 and adding the digit.
   • Remove the last digit from y by performing integer division by 10.
3. Comparison: After constructing the reversed integer, compare it to the original number x. If they are identical, x is a palindrome.

This approach effectively reconstructs the reversed number without needing the original number's length or auxiliary string manipulations.

Complexity

• Time complexity: The time complexity is O(log(n)) because we iterate through all the digits of the number x, where n is the input value.

• Space complexity: The space complexity is O(1) as we only use a few extra variables to store numbers, regardless of the input size.

Code

public class Solution {
    public bool IsPalindrome(int x) {
        if(x < 0)
            return false;

        var reverseNumber = 0;
        var y = x;

        while(y > 0)
        {
            reverseNumber = reverseNumber * 10 + (y % 10);
            y = y / 10;
        }

        return reverseNumber == x;
    }
}

Video

Conclusion

By reversing the integer numerically, this algorithm cleverly checks for palindromes without converting the number to a string, thus adhering to the problem's constraints while maintaining an efficient space complexity. This method ensures that we can handle large integers within the problem's constraints effectively.

This discussion provides a clear understanding of how to determine if a number is a palindrome via integer arithmetic, avoiding the pitfalls of converting to a string.

References

• Palindrome Number - LeetCode