Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Palindrome Number

EASYProblemSolveExternal Links

Description

Given an integer x, determine whether it is a palindrome. An integer is a palindrome when it reads the same forward and backward.

Return true if x is a palindrome, and false otherwise.

Note that negative numbers are never palindromes because the minus sign does not mirror symmetrically. For example, -121 reads as "121-" from right to left, which is different from "-121".

Examples

Example 1

Input: x = 121

Output: true

Explanation: 121 reads as 121 from left to right and from right to left. Both directions produce the same sequence of digits, so 121 is a palindrome.

Example 2

Input: x = -121

Output: false

Explanation: From left to right, it reads -121. From right to left, it would read 121-. The minus sign makes the forward and backward readings different, so negative numbers are never palindromes.

Example 3

Input: x = 10

Output: false

Explanation: From right to left, 10 reads as 01. Since 01 is not the same as 10, this number is not a palindrome. Any number ending in 0 (except 0 itself) cannot be a palindrome because leading zeros are not valid in number representation.

Constraints

  • -2^31 ≤ x ≤ 2^31 - 1

Editorial

Brute Force - String Conversion

Intuition

The simplest way to check if a number is a palindrome is to convert it to a string and then check if the string reads the same forwards and backwards.

Think of a palindrome like a word written on a piece of paper: if you flip the paper and read it in reverse, it spells the same thing. By turning the number into characters, we can directly compare the first character with the last, the second with the second-to-last, and so on.

We can use two pointers — one starting at the beginning and one at the end — moving inward. If every pair of characters matches, the string (and therefore the number) is a palindrome.

Step-by-Step Explanation

Let's trace through with x = 1221:

Step 1: Check if x is negative. x = 1221 ≥ 0, so we proceed.

Step 2: Convert x to string: s = "1221". Set left = 0, right = 3.

Step 3: Compare s[left] and s[right]: s[0] = '1', s[3] = '1'.

  • '1' == '1'? Yes, they match.
  • Move pointers inward: left = 1, right = 2.

Step 4: Compare s[left] and s[right]: s[1] = '2', s[2] = '2'.

  • '2' == '2'? Yes, they match.
  • Move pointers inward: left = 2, right = 1.

Step 5: left (2) > right (1), so the loop ends.

Step 6: All pairs matched. Return true — 1221 is a palindrome.

Now let's also see a failure case with x = 123:

Step 7: Convert x = 123 to string: s = "123". Set left = 0, right = 2.

Step 8: Compare s[0] = '1' and s[2] = '3'.

  • '1' == '3'? No, mismatch found.
  • Return false immediately — 123 is NOT a palindrome.

String Two-Pointer Palindrome Check on 1221 — Watch how two pointers converge from opposite ends, comparing characters at each step to verify the number reads the same both ways.

Algorithm

  1. If x is negative, return false (negatives are never palindromes)
  2. Convert x to its string representation s
  3. Set left = 0 and right = len(s) - 1
  4. While left < right:
    • If s[left] ≠ s[right], return false
    • Move left right by 1 and right left by 1
  5. Return true (all pairs matched)

Code

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        
        string s = to_string(x);
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
};
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        
        s = str(x)
        left, right = 0, len(s) - 1
        
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        
        return True
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        
        String s = String.valueOf(x);
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(d)

Where d is the number of digits in x. We compare at most d/2 pairs of characters, and string conversion itself takes O(d) time. Overall: O(d).

Space Complexity: O(d)

We create a string of length d to store the number's characters. This is extra space proportional to the number of digits.

Why This Approach Is Not Efficient

The string conversion approach works correctly but has two downsides:

  1. Extra space: Converting the integer to a string allocates O(d) memory for the character array. For very large numbers (up to 2^31 - 1 = 2,147,483,647 which has 10 digits), this is a small but unnecessary allocation.

  2. String overhead: String creation involves memory allocation, character copying, and in some languages (like Java) immutable string objects. These operations carry overhead compared to pure arithmetic.

The follow-up question asks: can we solve this without converting to a string? The answer is yes — we can reverse part of the number using arithmetic (modulo and division) and compare the reversed half directly. This eliminates both the string allocation and the conversion cost, achieving O(1) space.

Optimal Approach - Half Number Reversal

Intuition

Instead of converting the entire number to a string, we can compare the number mathematically by reversing only the second half of its digits.

Here is the key insight: if a number is a palindrome, then the first half of its digits must be a mirror image of the second half. So instead of reversing the whole number (which risks integer overflow for large values), we reverse just the back half and compare it with the front half.

We build the reversed half digit by digit. In each iteration, we peel the last digit off x (using x % 10) and append it to reversed_half (by multiplying reversed_half by 10 and adding the digit). At the same time, we shrink x by dividing it by 10. We stop when reversed_half becomes greater than or equal to x — at that point, we've processed exactly half (or just past half) of the digits.

For even-length numbers like 1221, after processing we get x = 12 and reversed_half = 12 — they are equal, confirming a palindrome. For odd-length numbers like 12321, we get x = 12 and reversed_half = 123 — the middle digit ends up in reversed_half, so we compare x with reversed_half / 10 to ignore it.

Two quick rejections save time: negative numbers are never palindromes, and numbers ending in 0 (except 0 itself) cannot be palindromes because no valid number starts with 0.

Step-by-Step Explanation

Let's trace through with x = 1221:

Step 1: Check edge cases: x = 1221 ≥ 0, and x % 10 = 1 ≠ 0. No quick rejection. Initialize reversed_half = 0.

Step 2: Extract last digit: x % 10 = 1221 % 10 = 1.

  • Build reversed_half: 0 × 10 + 1 = 1.
  • Shrink x: 1221 / 10 = 122.
  • Is reversed_half (1) ≥ x (122)? No → continue.

Step 3: Extract last digit: x % 10 = 122 % 10 = 2.

  • Build reversed_half: 1 × 10 + 2 = 12.
  • Shrink x: 122 / 10 = 12.
  • Is reversed_half (12) ≥ x (12)? Yes → stop.

Step 4: Compare: x == reversed_half? 12 == 12? YES.

Step 5: Return true — 1221 is a palindrome.

Now let's trace a non-palindrome with x = 123:

Step 6: x = 123. reversed_half = 0.

  • Digit = 3, reversed_half = 3, x = 12. reversed_half (3) < x (12) → continue.
  • Digit = 2, reversed_half = 32, x = 1. reversed_half (32) ≥ x (1) → stop.

Step 7: Compare: x == reversed_half? 1 == 32? No. x == reversed_half/10? 1 == 3? No.

Step 8: Return false — 123 is NOT a palindrome.

Half Number Reversal on 1221 — Watch how we peel digits from the right side of x and build a reversed number, stopping once we've processed exactly half the digits.

Now let's see the algorithm handle a non-palindrome and an odd-length palindrome:

Half Number Reversal on 123 (Non-Palindrome) — Watch how the algorithm quickly detects that 123 is not a palindrome when the two halves don't match after processing.

Algorithm

  1. Quick rejections:
    • If x < 0, return false (negative numbers are not palindromes)
    • If x % 10 == 0 and x != 0, return false (numbers ending in 0, except 0 itself, cannot be palindromes since no number starts with 0)
  2. Initialize reversed_half = 0
  3. While x > reversed_half:
    • Extract the last digit: digit = x % 10
    • Append to reversed half: reversed_half = reversed_half * 10 + digit
    • Remove last digit from x: x = x / 10
  4. Return x == reversed_half (even-length) OR x == reversed_half / 10 (odd-length, ignore middle digit)

Code

class Solution {
public:
    bool isPalindrome(int x) {
        // Negative numbers and numbers ending in 0 (except 0) are not palindromes
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        
        int reversedHalf = 0;
        
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }
        
        // Even length: x == reversedHalf
        // Odd length: x == reversedHalf / 10 (ignore middle digit)
        return x == reversedHalf || x == reversedHalf / 10;
    }
};
class Solution:
    def isPalindrome(self, x: int) -> bool:
        # Negative numbers and numbers ending in 0 (except 0) are not palindromes
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        
        reversed_half = 0
        
        while x > reversed_half:
            reversed_half = reversed_half * 10 + x % 10
            x //= 10
        
        # Even length: x == reversed_half
        # Odd length: x == reversed_half // 10 (ignore middle digit)
        return x == reversed_half or x == reversed_half // 10
class Solution {
    public boolean isPalindrome(int x) {
        // Negative numbers and numbers ending in 0 (except 0) are not palindromes
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        
        int reversedHalf = 0;
        
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }
        
        // Even length: x == reversedHalf
        // Odd length: x == reversedHalf / 10 (ignore middle digit)
        return x == reversedHalf || x == reversedHalf / 10;
    }
}

Complexity Analysis

Time Complexity: O(d/2) = O(d)

Where d is the number of digits in x. We only process half the digits because we stop when reversed_half ≥ x. Each iteration performs constant-time arithmetic. This is the same asymptotic complexity as the string approach but with a smaller constant factor.

Space Complexity: O(1)

We use only a single integer variable (reversed_half) to build the reversed number. No strings, arrays, or other data structures are allocated. This is an improvement over the string approach which requires O(d) space.