Palindrome Number

Easymath
Category: Fundamentals
Companies that ask this question:
AmazonGoogle

Approach

Palindrome Number

Problem Statement

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

An integer is a palindrome when it reads the same backward as forward.

  • For example, 121 is a palindrome while 123 is not.

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

Examples

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.

Approaches

Approach 1: Reverse Half the Number (Optimal)

Instead of reversing the entire number, we only reverse half of it and compare with the other half.

Key Insights:

  • Negative numbers are never palindromes (due to the minus sign)
  • Numbers ending in 0 are not palindromes (except 0 itself)
  • We only need to reverse half the digits to check

Algorithm:

  1. Handle edge cases: negative numbers and numbers ending in 0
  2. Reverse the second half of the number
  3. Compare with the first half
  4. For odd-length numbers, ignore the middle digit

Example: x = 1221

  • Initially: x = 1221, reversed = 0
  • Step 1: x = 122, reversed = 1
  • Step 2: x = 12, reversed = 12
  • Compare: 12 == 12 → palindrome

Example: x = 12321

  • Initially: x = 12321, reversed = 0
  • Step 1: x = 1232, reversed = 1
  • Step 2: x = 123, reversed = 12
  • Compare: 123 / 10 == 12 → palindrome (ignore middle digit)

Approach 2: Convert to String

Simple but uses extra space.

return str(x) == str(x)[::-1]

Complexity Analysis

Approach 1 (Reverse Half):

  • Time Complexity: O(log n) - process half the digits
  • Space Complexity: O(1) - constant extra space

Approach 2 (String):

  • Time Complexity: O(log n) - convert to string
  • Space Complexity: O(log n) - string storage

Edge Cases

  1. Negative numbers: Always return false
  2. Zero: Return true (palindrome)
  3. Single digit: Always palindrome
  4. Numbers ending in 0: False (except 0)
  5. Odd-length numbers: Ignore middle digit when comparing

Visual Intuition

Example: x = 1221

Original: 1221
Reverse:  1221  ✓ Palindrome

Process:
x = 1221, reversed = 0
x = 122,  reversed = 1   (extract 1)
x = 12,   reversed = 12  (extract 2)
Compare: 12 == 12 ✓

Example: x = 123

Original: 123
Reverse:  321  ✗ Not Palindrome

Process:
x = 123, reversed = 0
x = 12,  reversed = 3   (extract 3)
x = 1,   reversed = 32  (extract 2)
Compare: 1 != 32 ✗

Common Mistakes

  1. Not handling negative numbers: They're never palindromes
  2. Forgetting numbers ending in 0: Only 0 itself is a palindrome
  3. Reversing entire number: Unnecessarily complex
  4. Integer overflow: When reversing, might overflow (less of an issue in Python)

Related Problems

  • Reverse Integer
  • Reverse Linked List
  • Valid Palindrome

Solution

java
1/**
2 * Palindrome Number
3 * Time: O(log n) - half the digits
4 * Space: O(1)
5 */
6
7// Approach 1: Reverse Half (Optimal)
8class Solution {
9    public boolean isPalindrome(int x) {
10        // Negative numbers are not palindromes
11        // Numbers ending in 0 are not palindromes (except 0 itself)
12        if (x < 0 || (x % 10 == 0 && x != 0)) {
13            return false;
14        }
15        
16        int reversedHalf = 0;
17        while (x > reversedHalf) {
18            reversedHalf = reversedHalf * 10 + x % 10;
19            x /= 10;
20        }
21        
22        // For even length: x == reversedHalf
23        // For odd length: x == reversedHalf / 10 (ignore middle digit)
24        return x == reversedHalf || x == reversedHalf / 10;
25    }
26}
27
28// Approach 2: String Conversion
29class Solution2 {
30    public boolean isPalindrome(int x) {
31        if (x < 0) {
32            return false;
33        }
34        
35        String str = String.valueOf(x);
36        String reversed = new StringBuilder(str).reverse().toString();
37        return str.equals(reversed);
38    }
39}
40
Loading visualizer...