Question Link: Palindrome Number

Problem Statement :

Given an integer x, return true if x is a palindrome*, and false otherwise*.

Example 1:

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

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.

Constraints:

• -231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

Solution :

Approach: Reversing Half of the Number

Instead of reversing the entire number, we can reverse only the last half of the number. This approach is tricky because when we reverse the last half of the number, we don’t want the middle digit to be rev back to its original value. This can happen if the number has an odd number of digits. To resolve this, we can compare the first half of the number with the rev second half of the number.

Explanation :

We begin with an initial check to handle special cases:

If the input number x is negative, it cannot be a palindrome since palindromes are typically defined for positive numbers. In such cases, we immediately return false.
If x is non-zero and ends with a zero, it cannot be a palindrome because leading zeros are not allowed in palindromes. We return false for such cases.
We initialize two variables:

rev: This variable will store the rev second half of the digits of the number.
We enter a loop that continues until the first half of the digits (x) becomes less than or equal to the rev second half (rev):

Inside the loop, we extract the last digit of x using the modulo operator % and add it to the rev variable after multiplying it by 10 (shifting the existing digits to the left).
We then divide x by 10 to remove the last digit and move towards the center of the number.
Once the loop is completed, we have rev the second half of the digits. Now, we compare the first half of the digits (x) with the rev second half (rev) to determine if the number is a palindrome:

For an even number of digits, if x is equal to rev, then the number is a palindrome. We return true.
For an odd number of digits, if x is equal to rev / 10 (ignoring the middle digit), then the number is a palindrome. We return true.
If none of the above conditions are met, it means the number is not a palindrome, so we return false.
The code avoids the need for reversing the entire number by comparing only the necessary parts. This approach reduces both time complexity and memory usage, resulting in a more efficient solution.

Performance :

Code :

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0))return false;
        int rev=0;
        int original=x;
        while(x>rev) {
            rev = rev*10+(x%10);
            x/=10;
        }
        return (x==rev) || (x==rev/10);
    }
}