LeetCode. 9. Palindrome Number

[Link] https://leetcode.com/problems/palindrome-number/

Approach

A negative integer cannot be a palindrome because its minus sign appears only on the left. Any nonzero integer ending in zero also cannot be a palindrome: its reverse would begin with zero, which is not represented in the original integer.

Instead of converting the number to a string or reversing all its digits, reverse only the last half of the digits. Each loop iteration removes one digit from x and appends it to reversedHalf. The loop stops when reversedHalf has at least as many digits as the remaining x.

At that point, the original number is a palindrome exactly when the two halves match. For an even number of digits, compare x with reversedHalf. For an odd number of digits, the middle digit belongs to reversedHalf but has no counterpart, so discard it with integer division by 10 before comparing.

Only half the digits are reversed, so the intermediate value remains within the range of an int, including for Integer.MAX_VALUE. The algorithm takes O(log10 N) time and O(1) extra space.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }

        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        return x == reversedHalf || x == reversedHalf / 10;
    }
}