Palindrome Number — Without Converting to a String

The Palindrome Number problem asks you to decide whether a given integer reads the same forward and backward. It is a classic interview warm-up that sneaks in a clever optimization: you only need to reverse half the digits.

The Problem

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

Examples:

• x = 121 returns true.
• x = -121 returns false, because reversed it becomes 121-.
• x = 10 returns false, because reversed it becomes 01.

The follow-up question — “Could you solve it without converting the integer to a string?” — is the interesting half.

Intuition

Two easy early exits handle whole classes of inputs before any loop runs. Any negative number has a minus sign at the front and only digits at the back; reversed, the minus sign would land in the wrong place, so negatives are never palindromes. Any positive number ending in 0 would have a reversed form starting with 0, with fewer digits, so it cannot be a palindrome unless the number is 0 itself.

The main idea: you do not need to reverse the entire number. You only need to reverse the back half and compare it to the front half. Keep dividing the original by 10 (chopping digits off the right) while building up a reversed number from those same digits. When the reversed number becomes greater than or equal to the remaining original, you have processed at least half the digits. Compare. For odd digit counts, the middle digit ends up in the reversed half and can be discarded with one more division.

The half-reversal also dodges overflow concerns in fixed-width integer languages, because the reversed half always fits.

Explanation with Example

Walk through x = 1221 with reversed_half = 0.

• Iteration 1: reversed_half = 0 * 10 + 1 = 1, x = 122.
• Iteration 2: reversed_half = 1 * 10 + 2 = 12, x = 12.
• Loop ends because x is no longer strictly greater than reversed_half.
• x == reversed_half is true. Return true.

Walk through x = 12321:

• Iteration 1: reversed_half = 1, x = 1232.
• Iteration 2: reversed_half = 12, x = 123.
• Iteration 3: reversed_half = 123, x = 12.
• Loop ends. x == reversed_half // 10 is 12 == 12. Return true.

x = 1221  (even digit count)

step |   x     | reversed_half | loop cond (x > rh?)
-----+---------+---------------+--------------------
0  |  1221   |        0      | 1221 > 0    yes
1  |   122   |        1      |  122 > 1    yes
2  |    12   |       12      |   12 > 12   no  stop

final: x == reversed_half  -> 12 == 12  -> True

x = 12321 (odd digit count)

step |   x     | reversed_half | loop cond
-----+---------+---------------+----------------
0  | 12321   |        0      | yes
1  |  1232   |        1      | yes
2  |   123   |       12      | yes
3  |    12   |      123      |  12 > 123  no  stop

middle digit (3) sits in reversed_half; drop it:
x == reversed_half // 10  ->  12 == 12  -> True

Code

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        reversed_half = 0
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10
        return x == reversed_half or x == reversed_half // 10

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

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

Edge Cases

• Negative numbers: always return false. Handled by the early check.
• x = 0: palindrome. The early check carves out this case.
• Trailing zero like x = 10: not a palindrome. Caught by the early check.
• Single-digit x between 1 and 9: the loop runs once and x reduces to 0 with reversed_half equal to the digit. Comparison via x == reversed_half // 10 gives 0 == 0. True.
• Large x near INT_MAX: the reversed-half trick avoids overflow because the reversed half never exceeds the original.

Complexity Analysis

Time complexity is O(log n) where n is the value of x, because each iteration removes one decimal digit and there are about log10(x) digits.

Space complexity is O(1). We use a constant number of integer variables regardless of input size.

How to Explain It in an Interview

State the two early-exit conditions explicitly: negatives and trailing zeros (except zero). Then explain the half-reversal: chip digits off the right of x and append to reversed_half until the latter catches up. Cover both parity cases at the end with the dual return. Mention overflow safety as a bonus.

Related Problems

• Reverse Integer
• Valid Palindrome
• Palindrome Linked List

Wrap up

This is short, but it teaches digit-by-digit decomposition and a non-obvious optimization. The same “reverse the back half” trick shows up in problems involving linked lists, polynomial hashing, and certain dynamic programming check functions.