Topics › Basics › Know Basic Maths

Palindrome Number

Easy TUF ID 374 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a 32-bit signed integer n. Return true if n is a palindrome, meaning its decimal digits read the same from left to right and from right to left, and false otherwise. Negative numbers are not palindromes because the minus sign only appears at the front.

Constraints: -2^31 ≤ n ≤ 2^31 - 1. The follow-up asks you to do it without converting the number to a string.

Example 1

n = 121
answer = true       // 121 reversed is 121

Example 2

n = -121
answer = false      // reads 121- from the right

Example 3

n = 10
answer = false      // reads 01, which is 1, not 10

Approach 1: Brute force, via a string

Intuition. A palindrome is a string equal to its own reverse. Convert n to its decimal string, reverse it with StringBuilder, and compare. The negative check comes first so the - never gets involved.

Algorithm.

1. If n < 0, return false.
2. s = Integer.toString(n).
3. Return whether s equals reverse(s).

static boolean bruteForce(int n) {
    if (n < 0) return false;
    String s = Integer.toString(n);
    String reversed = new StringBuilder(s).reverse().toString();
    return s.equals(reversed);
}

Complexity. Time O(d) for d digits. Space O(d) for two strings and a builder.

A two-pointer scan over the characters (i from the left, j from the right, stop at the first mismatch) is also O(d) and avoids the reversed copy, but still needs the string. The follow-up wants us to avoid the string entirely.

Approach 2: Better, reverse the whole number arithmetically

Intuition. The digit loop from Reverse a number gives us the reversed value without any string: repeatedly take x % 10 and append it to an accumulator with rev = rev * 10 + digit. Then n is a palindrome exactly when rev == n.

One subtlety: the reversal of a valid int may not fit in an int. 2147483647 reversed is 7463847412. If rev were an int it would overflow and could, in principle, wrap around to equal n by accident. Keeping rev in a long removes the problem, because any 10-digit reversal is below 10^10.

Algorithm.

1. If n < 0, return false.
2. rev = 0L, x = n.
3. While x > 0: rev = rev * 10 + x % 10, x /= 10.
4. Return rev == n.

static boolean better(int n) {
    if (n < 0) return false;
    long rev = 0;
    int x = n;
    while (x > 0) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return rev == n;
}

Complexity. Time O(d). Space O(1).

Note that n = 0 works without a special case: the loop does not run and 0 == 0. Numbers ending in 0 such as 10 reverse to 1, which is never equal to the original, so they are correctly rejected.

Approach 3: Optimal, reverse only half of the digits

Intuition. We do not need the entire reversal. If we reverse just the right half of the digits and compare it with the left half, the comparison is the same and the reversed value is at most half as long as n, so it can never overflow even in an int.

How do we know when we have reached the middle without counting digits first? Keep peeling digits from n into rev. While n > rev, the remaining left part still has at least as many digits as the reversed right part, so we have not passed the middle. The moment n <= rev we stop:

• for an even number of digits (1221), n and rev both hold two digits: 12 and 12;
• for an odd number of digits (12321), rev has taken the middle digit too: n = 12, rev = 123. The middle digit does not need to match anything, so compare n with rev / 10.

There is one input family that breaks the “stop when n <= rev” rule: numbers ending in 0. For 10, the first step gives rev = 0, n = 1, and n > rev continues, then rev = 1, n = 0, and n == rev says true, which is wrong. Any multiple of 10 (other than 0 itself) cannot be a palindrome because its first digit is not 0, so reject those up front.

Algorithm.

1. If n < 0, or n ends in 0 but is not 0, return false.
2. rev = 0.
3. While n > rev: rev = rev * 10 + n % 10, n /= 10.
4. Return n == rev || n == rev / 10.

static boolean optimal(int n) {
    if (n < 0 || (n % 10 == 0 && n != 0)) return false;
    int rev = 0;
    while (n > rev) {
        rev = rev * 10 + n % 10;
        n /= 10;
    }
    return n == rev || n == rev / 10;
}

Dry run on n = 12321:

n == rev is false but n == rev / 10 is 12 == 12, so the answer is true.

Dry run on n = 1221: (1221, 0) -> (122, 1) -> (12, 12), stop, n == rev, true.

Dry run on n = 123: (123, 0) -> (12, 3) -> (1, 32), stop; 1 != 32 and 1 != 3, so false.

Complexity. Time O(d), about half the iterations of the full reversal. Space O(1), and rev never exceeds n, so no overflow is possible even with int.

Edge cases and pitfalls

• Negative numbers are never palindromes. Check first; otherwise % would produce negative digits.
• Zero is a palindrome. The n % 10 == 0 rejection in Approach 3 must exclude n == 0 explicitly.
• Multiples of 10 (10, 100, 1000000) are never palindromes. Approach 3 must reject them before the loop, or the loop’s stopping rule misfires.
• Overflow in full reversal. 2147483647 reversed is 7463847412, which exceeds int. Use a long accumulator (Approach 2) or only reverse half (Approach 3). The largest palindrome that fits in an int is 2147447412; it is in the tests.
• Odd versus even digit count. With the half-reversal, remember the n == rev / 10 case for odd lengths. Forgetting it makes 12321 fail; forgetting the n == rev case makes 1221 fail.
• Single digits are palindromes. The loop runs once and n == rev / 10 handles it (for 7: n = 0, rev = 7, 0 == 0).

Related problems

• Reverse a number is the full-reversal subroutine used by Approach 2, including the overflow discussion.
• Count all Digits of a Number introduces the % 10 and / 10 digit loop.
• Check if String is Palindrome or Not does the same check on characters, recursively.
• Check if LL is palindrome or not applies the “compare the first half with the reversed second half” idea to a linked list.