Palindrome Number – LeetCode 9 Solution

A palindrome number reads the same forward and backward. This problem is a classic example of simple logic-based programming and is widely used in coding interviews to test problem-solving skills and understanding of fundamental concepts. In this blog post, we’ll explore various ways to solve the Palindrome Number problem (LeetCode 9) in Java.

Problem Statement

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

A palindrome is a number that remains the same when its digits are reversed.

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:

-231 <= x <= 231 - 1

Understanding the Problem

A number is considered a palindrome if it reads the same forwards and backwards. For instance, 121 is a palindrome, whereas -121 is not due to the negative sign.

There are three possible approaches to solve this problem in Java:

1. String Conversion Method – Convert the integer to a string and compare it with its reverse.
2. Reversing Half of the Number – Reverse only half of the integer and check if it matches the other half.
3. Full Reversal and Comparison – Reverse the integer completely and check if it equals the original number.

Let’s examine each method in detail.

Approach 1: String Conversion Method

This approach is straightforward: convert the number to a string, then check if the string reads the same forwards and backwards.

Steps:

1. Convert the integer x to a string.
2. Check if the string is equal to its reverse.

Code Implementation:

public class PalindromeNumber {
    public boolean isPalindrome(int x) {
        // Negative numbers are not palindromes
        if (x < 0) {
            return false;
        }

        // Convert the number to a string
        String original = Integer.toString(x);

        // Reverse the string
        String reversed = new StringBuilder(original).reverse().toString();

        // Check if the original string equals the reversed string
        return original.equals(reversed);
    }

    public static void main(String[] args) {
        PalindromeNumber solution = new PalindromeNumber();
        System.out.println(solution.isPalindrome(121));  // Output: true
        System.out.println(solution.isPalindrome(-121)); // Output: false
    }
}

Time Complexity: O(n), where n is the number of digits in x
Space Complexity: O(n), as we are creating new string objects.

This approach is simple but not optimal in terms of space complexity.

Approach 2: Reversing Half of the Number

In this approach, we reverse only half of the digits and compare the reversed half with the other half. This method doesn’t require extra space for string conversion and is more efficient for large numbers.

Steps:

1. Return false for negative numbers and numbers ending in 0 (except 0 itself).
2. Reverse the last half of the digits by continuously popping the last digit of x and building the reversed number.
3. Compare the reversed half with the remaining half.

Code Implementation:

public class PalindromeNumber {
    public boolean isPalindrome(int x) {
        // Negative numbers or numbers ending in 0 are not palindromes (except 0)
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reversedHalf = 0;
        while (x > reversedHalf) {
            // Append last digit of x to reversedHalf
            reversedHalf = reversedHalf * 10 + x % 10;
            // Remove last digit from x
            x /= 10;
        }

        // Check if either x equals reversedHalf (odd length) or
        // x equals reversedHalf/10 (even length)
        return x == reversedHalf || x == reversedHalf / 10;
    }

    public static void main(String[] args) {
        PalindromeNumber solution = new PalindromeNumber();
        System.out.println(solution.isPalindrome(121));  // Output: true
        System.out.println(solution.isPalindrome(1221)); // Output: true
    }
}

Time Complexity: O(log10(x)), since we’re only iterating through half of the digits.
Space Complexity: O(1), as no additional data structures are used.

This is the most efficient solution and works well for any integer within the constraints.

Approach 3: Full Reversal and Comparison

In this approach, we reverse the entire integer and then compare it to the original integer.

Steps:

1. If x is negative, return false.
2. Reverse the integer using modulo and division operations.
3. Compare the reversed integer to the original integer.

Code Implementation:

public class PalindromeNumber {
    public boolean isPalindrome(int x) {
        // Negative numbers are not palindromes
        if (x < 0) {
            return false;
        }

        int original = x;
        int reversed = 0;

        while (x != 0) {
            int digit = x % 10;
            // Check for integer overflow
            if (reversed > (Integer.MAX_VALUE - digit) / 10) {
                return false;
            }
            reversed = reversed * 10 + digit;
            x /= 10;
        }

        // Check if the reversed number matches the original
        return original == reversed;
    }

    public static void main(String[] args) {
        PalindromeNumber solution = new PalindromeNumber();
        System.out.println(solution.isPalindrome(121));  // Output: true
        System.out.println(solution.isPalindrome(-121)); // Output: false
    }
}

Time Complexity: O(log10(x)), similar to the previous approach.
Space Complexity: O(1), as no additional space is used except for integer variables.

However, this solution involves reversing the entire integer, which may lead to integer overflow in languages without built-in overflow protection. In Java, we handle it by checking for overflow before adding a new digit to reversed.

In conclusion, the Reversing Half of the Number approach is the most efficient solution for palindrome number, with constant space complexity and logarithmic time complexity. It avoids potential overflow issues and minimizes memory usage, making it ideal for handling larger numbers.

For other Leetcode problems, visit Leetcode Problems and their solutions.