Palindrome Number

def is_palindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    rev = 0
    while x > rev:
        rev = rev * 10 + x % 10
        x //= 10
    return x == rev or x == rev // 10

Palindrome Number. Given an integer x, return true if it reads the same forwards and backwards. The catch: do it without turning x into a string.

One twenty one reads one, two, one both ways: true. Minus one twenty one, backwards, is one twenty one minus: false. Ten backwards is zero one: false.

The easy way compares the string with its reverse. But that builds a string, one extra character per digit, which the catch rules out. Reversing the whole number can overflow.

The key idea: reverse only half. First, negatives and numbers ending in zero, except zero, are false. Then peel the last digit off with x mod ten, and push it onto a second number: rev times ten, plus the digit. Stop once rev catches up with x. For one two two one, two peels leave twelve and twelve: a match. It's the linked list fold in half, done with arithmetic.

In code, the easy cases return false. While x is bigger than rev, move one digit across. Then x must equal rev, or rev with its last digit dropped.

Now one twenty one. Pop the one: rev is one, x is twelve. Twelve is still bigger, so pop the two: rev is twelve, x is one. Rev has caught up. An odd length leaves the middle digit on rev, so drop it: twelve becomes one. One equals one: true.

Each step peels one digit, and we stop halfway: log n time. Just two numbers: constant space.

Reject the easy falses, peel half the digits, compare. That's Palindrome Number.