9. Palindrome Number - Solution & Explanation

The problem

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

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Follow up: Could you solve it without converting the integer to a string?

Approach overview

Problem Overview: Given an integer x, determine whether it reads the same forward and backward. A number like 121 is a palindrome, while 123 is not. The catch: negative numbers and numbers ending in 0 (except 0 itself) cannot be palindromes.

Approach 1: String Conversion Method (Time: O(d), Space: O(d))

Convert the integer into a string and compare characters from both ends. You can either reverse the string and check equality with the original, or use two pointers starting at the first and last character and move them inward while comparing digits. The key insight is that palindrome validation becomes a simple symmetric comparison problem once the number is represented as text. This approach is straightforward and easy to implement in languages with strong string utilities. The tradeoff is extra memory for the string representation.

This method relies on basic operations from math and simple character comparisons. It’s often the fastest way to write a correct solution during early practice or when code clarity matters more than strict memory optimization.

Approach 2: Reversing Half of the Number (Time: O(log n), Space: O(1))

This approach avoids string conversion and works purely with integer arithmetic. Repeatedly extract the last digit using x % 10 and build a reversed value using reversed = reversed * 10 + digit. Instead of reversing the entire number, stop when the reversed half becomes greater than or equal to the remaining half. At that point you’ve processed half the digits.

The key insight: a palindrome mirrors around its center. If the reversed second half equals the remaining first half, the number is a palindrome. For numbers with an odd number of digits, discard the middle digit by dividing the reversed half by 10. This avoids overflow and reduces unnecessary work.

This technique is a classic math-based digit manipulation problem. Conceptually it resembles a two‑pointer comparison, but performed numerically instead of on an array or string.

Recommended for interviews: Reversing half of the number. Interviewers prefer it because it demonstrates control over digit extraction, edge case handling, and constant-space reasoning. The string approach shows you understand the core palindrome concept, but the half-reversal method shows stronger algorithmic thinking and attention to constraints.

Approach 1: String Conversion Method

In this method, we convert the integer to a string and check if it reads the same forwards and backwards. This approach is straightforward and leverages the built-in string operations.

Python

def isPalindrome(x: int) -> bool:
    if x < 0:
        return False
    return str(x) == str(x)[::-1]

Java

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        String str = Integer.toString(x);
        int n = str.length();
        for (int i = 0; i < n / 2; i++) {
            if (str.charAt(i) != str.charAt(n - i - 1)) return false;
        }
        return true;
    }
}

C++

#include <iostream>

bool isPalindrome(int x) {
    if (x < 0) return false;
    std::string str = std::to_string(x);
    int n = str.size();
    for (int i = 0; i < n / 2; ++i) {
        if (str[i] != str[n - i - 1]) return false;
    }
    return true;
}

JavaScript

function isPalindrome(x) {
    if (x < 0) return false;
    const str = x.toString();
    const n = str.length;
    for (let i = 0; i < n / 2; i++) {
        if (str[i] !== str[n - i - 1]) return false;
    }
    return true;
}

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

bool isPalindrome(int x) {
    if (x < 0) return false;
    char str[12];
    sprintf(str, "%d", x);
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - i - 1]) return false;
    }
    return true;
}

public class Solution {
    public bool IsPalindrome(int x) {
        if (x < 0) return false;
        string str = x.ToString();
        int n = str.Length;
        for (int i = 0; i < n / 2; i++) {
            if (str[i] != str[n - i - 1]) return false;
        }
        return true;
    }
}

After checking if the number is negative, the function converts the number to a string and uses Python slicing to reverse the string. It compares the original and reversed string to check if they are the same.

Complexity

Time Complexity: O(n), where n is the length of the number when converted to a string.
Space Complexity: O(n) due to the string conversion.

Try this approach in the editor

Approach 2: Reversing Half of the Number

This approach avoids the use of string conversions by reversing half of the digits of the number and comparing the two halves. This is more memory efficient as it only creates a few integer variables.

Python

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

Java

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

C++

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

JavaScript

function isPalindrome(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
    let reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    return x === reversedHalf || x === Math.floor(reversedHalf / 10);
}

#include <stdbool.h>

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

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

The function handles special cases for negative numbers and those ending in zero. It reverses the second half of the number and compares it with the first half, using integer operations for efficiency.

Complexity

Time Complexity: O(log₁₀(n)), where n reflects the number of digits in x.
Space Complexity: O(1), only a few integer variables are used.

Try this approach in the editor

Approach 3: Reverse Half of the Number

First, we determine special cases:

If x < 0, then x is not a palindrome, directly return false;
If x > 0 and the last digit of x is 0, then x is not a palindrome, directly return false;
If the last digit of x is not 0, then x might be a palindrome, continue the following steps.

We reverse the second half of x and compare it with the first half. If they are equal, then x is a palindrome, otherwise, x is not a palindrome.

For example, for x = 1221, we can reverse the second half from "21" to "12" and compare it with the first half "12". Since they are equal, we know that x is a palindrome.

Let's see how to reverse the second half.

For the number 1221, if we perform 1221 bmod 10, we will get the last digit 1. To get the second last digit, we can first remove the last digit from 1221 by dividing by 10, 1221 / 10 = 122, then get the remainder of the previous result divided by 10, 122 bmod 10 = 2, to get the second last digit.

If we continue this process, we will get more reversed digits.

By continuously multiplying the last digit to the variable y, we can get the number in reverse order.

In the code implementation, we can repeatedly "take out" the last digit of x and "add" it to the end of y, loop until y \ge x. If at this time x = y, or x = y / 10, then x is a palindrome.

The time complexity is O(log_{10}(n)), where n is x. For each iteration, we will divide the input by 10, so the time complexity is O(log_{10}(n)). The space complexity is O(1).

TypeScript

function isPalindrome(x: number): boolean {
    if (x < 0 || (x > 0 && x % 10 === 0)) {
        return false;
    }
    let y = 0;
    for (; y < x; x = ~~(x / 10)) {
        y = y * 10 + (x % 10);
    }
    return x === y || x === ~~(y / 10);
}

func isPalindrome(x int) bool {
	if x < 0 || (x > 0 && x%10 == 0) {
		return false
	}
	y := 0
	for ; y < x; x /= 10 {
		y = y*10 + x%10
	}
	return x == y || x == y/10
}

Rust

impl Solution {
    pub fn is_palindrome(mut x: i32) -> bool {
        if x < 0 || (x != 0 && x % 10 == 0) {
            return false;
        }
        let mut y = 0;
        while x > y {
            y = y * 10 + x % 10;
            x /= 10;
        }
        x == y || x == y / 10
    }
}

PHP

class Solution {
    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        if ($x < 0 || ($x && $x % 10 == 0)) {
            return false;
        }
        $y = 0;
        while ($x > $y) {
            $y = $y * 10 + ($x % 10);
            $x = (int) ($x / 10);
        }
        return $x == $y || $x == (int) ($y / 10);
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
String Conversion Method	Time Complexity: O(n), where n is the length of the number when converted to a string. Space Complexity: O(n) due to the string conversion.
Reversing Half of the Number	Time Complexity: O(log₁₀(n)), where n reflects the number of digits in x. Space Complexity: O(1), only a few integer variables are used.
Reverse Half of the Number	–

Complexity analysis

Approach	Time	Space	When to Use
String Conversion Method	O(d)	O(d)	When simplicity and readability matter more than memory usage
Reverse Half of the Number	O(log n)	O(1)	Preferred interview solution; avoids string conversion and uses constant space

Frequently asked questions

Is Palindrome Number easy or hard?

Palindrome Number is classified as an Easy problem. The string-based solution is straightforward, but the constant-space mathematical approach introduces useful concepts like digit extraction and partial number reversal.

Palindrome Number Python/Java solution

In Python or Java, you can either convert the integer to a string and check if it equals its reverse, or implement the mathematical approach that reverses half of the digits using modulo and division. The math approach is typically preferred in interviews because it runs in O(log n) time and constant space.

How to solve Palindrome Number in O(log n)?

Repeatedly remove the last digit of the number using x % 10 and append it to a reversed variable using reversed = reversed * 10 + digit. Stop when the reversed value becomes greater than or equal to the remaining number. If both halves match (or match after removing the middle digit for odd lengths), the number is a palindrome.

What is the best approach for Palindrome Number?

The most efficient approach reverses only half of the digits using integer arithmetic. Extract digits with modulo and build a reversed half until it matches the remaining half. This method runs in O(log n) time and uses O(1) space because it avoids converting the number to a string.

Is Palindrome Number asked at Google/Amazon/Meta?

Palindrome Number is a common screening problem across major tech companies. Variations of digit reversal and palindrome checks appear in interview preparation sets used by Google, Amazon, Meta, and Microsoft to test basic algorithmic thinking and edge case handling.

What data structure is used in Palindrome Number?

The optimal solution uses no additional data structures and works directly with integer arithmetic. The simpler implementation converts the number to a string and compares characters from both ends using a two-pointer style comparison.

What is the time complexity of Palindrome Number?

The optimal solution runs in O(log n) time because the algorithm processes each digit once. Since the number of digits in an integer grows logarithmically with its value, reversing half the digits requires proportional work.

Palindrome Number solution and explanation

The problem

Approach overview

Approach 1: String Conversion Method

Approach 2: Reversing Half of the Number

Approach 3: Reverse Half of the Number

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Palindrome Number solution and explanation

The problem

Approach overview

Approach 1: String Conversion Method

Approach 2: Reversing Half of the Number

Approach 3: Reverse Half of the Number

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems