#9 Palindrome Number

frequently reported atTCS Infosys Bloomberg Google Microsoft Amazon

the problem

In plain words

Given an int x, return true if its decimal digits read the same from left to right and from right to left. Try to do it without turning x into a String.

in x = 121

out true

in x = -121

out false

Backwards it reads "121-".

in x = 10

out false

Backwards it reads "01".

−2³¹ ≤ x ≤ 2³¹ − 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternDigit peeling (% 10 and / 10)

Reverse only the second half of the number and compare it with the first half. Half a number can never overflow, and you stop as soon as the reversed half catches up.

solutions

From brute force to optimal

Integer.toString(x), reverse it with a StringBuilder, compare.

s = Integer.toString(x).
Return s equals its reverse (negatives fail by themselves).

timeO(d)

d ≤ 10 digits, copied and compared.

spaceO(d)

Two strings.

javajava.util.*

1class Solution {2    public boolean isPalindrome(int x) {3        String s = Integer.toString(x);                          // "-121" reversed is "121-": negatives fail by themselves4        return new StringBuilder(s).reverse().toString().equals(s);5    }6}

Build the full reverse with % 10 and / 10 and compare it with x.

Negative → false.
rev = rev * 10 + rest % 10 for every digit (in a long).
Return rev == x.

timeO(d)

One step per digit.

spaceO(1)

But it needs a long: reversing 2,147,483,647 overflows an int.

javajava.util.*

1class Solution {2    public boolean isPalindrome(int x) {3        if (x < 0) return false;4        long rev = 0;                                            // long: reversing 2147483647 would overflow an int5        for (int rest = x; rest > 0; rest /= 10) rev = rev * 10 + rest % 10;6        return rev == x;7    }8}

Move digits from the end of x into half until half ≥ x, then compare the two halves.

x < 0, or x ends in 0 (and isn't 0) → false.
While x > half: half = half * 10 + x % 10; x /= 10.
Return x == half || x == half / 10.

timeO(d)

Only d/2 loop steps.

spaceO(1)

Two ints; half never overflows.

javajava.util.*

1class Solution {2    public boolean isPalindrome(int x) {3        if (x < 0 || (x % 10 == 0 && x != 0)) return false;     // negatives, and 10, 120, ... (no leading zeros)4        int half = 0;5        while (x > half) {                                       // stop once we have reversed half the digits6            half = half * 10 + x % 10;7            x /= 10;8        }9        return x == half || x == half / 10;                      // even length, or odd length (drop the middle digit)10    }11}

in the room

How to say it in the interview

talk track

Start with the quick rejects: negatives, and numbers ending in 0.
Explain why half: it avoids overflow and halves the work. Then the odd-length case: drop the middle digit with half / 10.

traps

Forgetting that 10, 100, 120 can't be palindromes — without that check, the half-reverse loop says 10 is one.
Reversing the full number in an int.

what they ask next

Follow-ups

Palindrome in another base, e.g. binary?

Same idea with % 2 and / 2 (or bit shifts) instead of % 10 and / 10.

before you submit

Edge cases to test

Negative numbers → false (the minus sign has no partner)
Numbers ending in 0 (10, 120) → false, except 0 itself
Single digit → true
Odd vs even digit count

practise next