9. Palindrome Number

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:

  • -231 <= x <= 231 - 1

Problem Description

The given problem asks us to determine if an integer x is a palindrome. An integer is a palindrome when it reads the same backward as forward. For example, the integers 121 and 12321 are palindromes, while 123 and -121 are not.

Intuition

The key idea to solving this problem is to reverse half of the number and compare it with the other half. If both halves are the same, then the number is a palindrome. We can do this comparison without using extra space, which improves the efficiency of the algorithm. To achieve this, we follow these steps:

  • If a number is negative or if it is a multiple of 10 (except for 0), it cannot be a palindrome; such cases return False immediately. For example, -121 cannot be a palindrome because the minus sign does not reverse, and 10 is not a palindrome because no integer starting with 0 can be a palindrome (except for 0 itself).
  • We can then divide the number into two halves. However, instead of dividing the number explicitly, we construct the half reverse incrementally. We initialize a variable y to zero and then repeatedly take the last digit of x (by x % 10) and add it to y after first multiplying y by 10 (to shift its digits left).
  • We do this process while y is less than x. Eventually, x will be reduced to either the first half or just short of the half of the original number (in the case of an odd number of digits), while y will contain the reversed second half. By stopping when y becomes greater than or equal to x, we prevent the need to handle special cases for odd digit numbers.
  • Finally, we check if x is equal to y (which happens when the length of the number is even) or if x is equal to y divided by 10 (to remove the middle digit in the case of an odd length number). If either condition is true, the original number is a palindrome, and we return True; otherwise, we return False.

The given Python solution implements this logic within the isPalindrome function.

Solution Approach

The implementation of the palindrome check for an integer x in Python uses a straightforward approach without the need for additional data structures like arrays or strings. Here is the step-by-step walkthrough of the code and the logic behind the implementation:

  • First, the code checks for the edge cases where the number cannot be a palindrome. This includes any negative numbers and any positive numbers that end in 0 – except for 0 itself. In Python, the expression (x and x % 10 == 0) will return True for all multiples of 10 except 0 because, in Python, 0 is considered as False. Thus, if x < 0 or (x and x % 10 == 0): checks if x is a negative number or a non-zero multiple of 10, returning False immediately if either is true.
  • The algorithm initializes a variable y to zero. This variable serves as a reversed version of the second half of x.
  • Then, the algorithm enters a while loop that continues to iterate as long as y is less than x. Inside this loop:
    • The last digit of x is appended to y using y = y * 10 + x % 10. The multiplication by 10 moves the current digits of y to the left before adding the new digit.
    • The last digit is removed from x using x //= 10, which is integer division by 10 in Python.
  • When the loop ends, two possible scenarios exist:
    • If the original number x had an even number of digits, x and y would now be equal.
    • If the original number x had an odd number of digits, x would be y with the middle digit removed from y.
  • To check if x is a palindrome, the condition return x in (y, y // 10) is used, which returns True if x matches either y or y divided by 10 (discarding the middle digit for the odd digit case).

The implementation utilizes the modulus operator % for extracting digits, integer division // for truncating digits, and a while loop to construct the reversed half incrementally. The advantage of this solution is that it operates in place and requires constant space, as it doesn’t use extra memory proportional to the number of digits in x.

Example Walkthrough

Let’s illustrate the solution approach with the example of x = 1221. We want to determine if x is a palindrome using the steps provided.

  1. First, we check if x is less than 0 or if x is a multiple of 10, but not 0 itself. Since 1221 is a positive number and not a multiple of 10, we proceed to the next step.
  2. We initialize y to 0. This y variable will be used to store the reversed number.
  3. We enter the while loop and iterate as long as y < x. Here’s how the loop progresses:
    • First iteration:
      • y = 0 * 10 + 1221 % 10 results in y = 1
      • x = 1221 // 10 leads to x = 122
    • Second iteration:
      • y = 1 * 10 + 122 % 10 results in y = 12
      • x = 122 // 10 leads to x = 12
  4. At this point, y is no longer less than x. The loop ends, and we have two halves x = 12 and y = 12.
  5. Finally, we check if x == y or x == y // 10. Since 12 is equal to 12, the function will return True, confirming that 1221 is indeed a palindrome.

This walkthrough demonstrates how the algorithm processes an input number through a series of steps to determine if it is a palindrome without requiring additional space for storing reversed numbers or strings.

Solution Implementation

class Solution {
public:
    bool isPalindrome(int x) {
        // If the number is negative, it cannot be a palindrome
        if (x < 0) {
            return false;
        }

        long reverse = 0;  // Variable to store the reversed number
        int xcopy = x;     // Keep a copy of the original number to compare later

        // Reverse the number by extracting each digit and building the reversed number
        while (x > 0) {
            reverse = (reverse * 10) + (x % 10);  // Add the last digit of x to the reversed number
            x /= 10;  // Remove the last digit from x
        }

        // Check if the reversed number is equal to the original number
        return reverse == xcopy;        
    }
};
Copied!
class Solution {
    public boolean isPalindrome(int x) {
        // If the number is negative or ends with a 0 (but is not 0), it's not a palindrome
        if(x < 0 || (x != 0 && x % 10 == 0)) return false;
        
        int check = 0;  // This variable will store the reversed half of the number
        
        // Continue reversing digits until the original number is smaller than or equal to the reversed half
        while(x > check){
            // Reverse the last digit and add it to 'check'
            check = check * 10 + x % 10;
            // Remove the last digit from the original number
            x /= 10;
        }

        // If the number equals the reversed half or equals the reversed half divided by 10
        // (in case of odd-length numbers), then it's a palindrome
        return (x == check || x == check / 10);
    }
}
Copied!
class Solution:
 def isPalindrome(self, x: int) -> bool:
     # If the number is negative, it cannot be a palindrome
     if x < 0:
         return False
     reverse = 0  # Variable to store the reversed number
     xcopy = x  # Keep a copy of the original number to compare later
     # Reverse the number by extracting each digit and building the reversed number
     while x > 0:
         reverse = (reverse * 10) + (x % 10)  # Add the last digit of x to the reversed number
         x //= 10  # Remove the last digit from x 
     # Check if the reversed number is equal to the original number
     return reverse == xcopy
Copied!
bool isPalindrome(int x){
    // If the number is negative or ends with a 0 (but is not 0), it can't be a palindrome
    if(x < 0 || (x != 0 && x % 10 == 0)) return false;

    int check = 0; // This variable will store the reversed half of the number

    // Continue until the original number is smaller than or equal to the reversed half
    while(x > check){
        // Reverse the last digit and add it to 'check'
        check = check * 10 + x % 10;
        // Remove the last digit from the original number
        x /= 10;
    }

    // If the original number equals the reversed half or the reversed half divided by 10
    // (in case of odd-length numbers), then it's a palindrome
    return (x == check || x == check / 10);
}
Copied!
public class Solution {
    public bool IsPalindrome(int x) 
    {
        // If the number is negative or if it ends with a 0 (but is not 0 itself), it cannot be a palindrome
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;

        int reversedHalf = 0; // This will store the reversed half of the number
        while (x > reversedHalf) // Keep going until the original number is smaller than or equal to the reversed half
        {
            // Reverse the last digit and add it to the reversedHalf
            reversedHalf = reversedHalf * 10 + x % 10;
            // Remove the last digit from the original number
            x /= 10;
        }

        // A number is a palindrome if the first half is equal to the reversed second half
        // Or if the first half is equal to the second half divided by 10 (to handle odd-length numbers)
        return x == reversedHalf || x == reversedHalf / 10;
    }
}
Copied!
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
    // paso#1: Initialize invertido to 0 and aux with the value of x
    let invertido = 0;
    let aux = x;

    while (aux > 0) {
        // paso#2: Get the last digit of the number
        let val = aux % 10;
        // paso#3: Build the reversed number by adding the last digit to the new number
        invertido = val + (invertido * 10);
        // paso#4: Remove the last digit from aux
        aux = Math.floor(aux / 10);
    }

    // paso#5: Compare the reversed number with the original number to check if it's a palindrome
    if (invertido == x) return true;
    return false;
};
Copied!
function isPalindrome(x: number): boolean {
    // Convert the number to a string to easily compare digits
    const char = x.toString()
    let start = 0; // Pointer to the beginning of the string
    let end = char.length - 1; // Pointer to the end of the string

    // Compare characters from both ends towards the center
    while (start < end) {

        // If characters at the start and end are different, it's not a palindrome
        if (char[start] !== char[end]) return false

        start++; // Move the start pointer to the right
        end--;   // Move the end pointer to the left
    }

    // If we reach this point, the number is a palindrome
    return true
    
};
Copied!
class Solution {
    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        // paso#1: Initialize $revertido to 0 and $aux with the value of $x
        $revertido = 0;
        $aux = $x;
 
        while($aux > 0){
            // paso#2: Get the last digit of the number
            $val = $aux % 10;
            // paso#3: Build the reversed number by adding the last digit to the new number
            $revertido = $val + ($revertido * 10);
            // paso#4: Remove the last digit from $aux
            $aux = floor($aux / 10);
        }
 
        // paso#5: Compare the reversed number with the original number to check if it's a palindrome
        if($revertido == $x) return true;
        else return false;
    }
}
Copied!
class Solution {
    // Main function to check if the number is a palindrome
    func isPalindrome(_ x: Int) -> Bool {
        // If the number is negative, it's not a palindrome
        return x < 0 ? false : method(x: x) == x // Compare the reversed number with the original number
    }

    // Helper method to reverse the number
    private func method(x: Int) -> Int {
        var r = 0
        var x = x
        while x != 0 { 
            // Extract the last digit and append it to the reversed number
            r = r * 10
            r = r + x % 10
            x /= 10 // Remove the last digit from the original number
        }
        // Return 0 if the reversed number overflows 32-bit integer range
        return (r < Int32.min || r > Int32.max) ? 0 : r
    }
}
Copied!
class Solution {
    fun isPalindrome(x: Int): Boolean {
        // Convert the integer to a string and compare it with its reversed version
        return x.toString().reversed() == x.toString()  // Return true if the number is equal to its reversed version, otherwise false
    }
}
Copied!
class Solution {
  bool isPalindrome(int x) {
    int reverse = 0;
    int copy = x;

    //The loop break when the copy of original number becomes zero
    //Also negative number cannot be a palindrome
    while (copy > 0) {
      final digit = copy % 10;
      reverse = reverse * 10 + digit;
      copy = copy ~/ 10;
    }

    return reverse == x;
  }
}
Copied!
func isPalindrome(x int) bool {
    // Converting the integar to a string
    strnumber := strconv.Itoa(x)
    strlen := len(strnumber)
    // Checking if the integar is less than or is zero and returning false
    // if matches (Negative numbers cannot be a palindrome)
    if x < 0 {
        return false
    } else if x == 0 {
        return true // 0 is a palindrome
    // Checking if the last digit is zero 
    // (Number ending with zero cannot be a palindrome)
    } else if rune(strnumber[strlen-1]) == '0' {
        return false
    } else {
    // Creating a for-loop which loops on half of the length of the 
    // string  
        for i := 0; i < int(math.Round(float64(strlen/2))); i++ {
    // Verifying if the numbers are equal by checking for a match on  
    // the opposite side of the string.
            if strnumber[i] != strnumber[strlen-1-i] {
                return false
            }
        }
        return true
    }
}
Copied!

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of digits in the input integer x. This is because the loop runs until the reversed number y is greater than or equal to the input number x, which happens after n/2 iterations in the worst case (when the whole number is a palindrome).

Each iteration involves a constant number of operations: a multiplication, an addition, a modulus operation, and a division, none of which depend on the size of x. Therefore, these operations do not affect the linear time complexity with respect to the number of digits in x.

The space complexity is O(1), as the amount of extra space used does not grow with the size of the input. The variables x and y are the only extra space used, and they store integers, which take constant space regardless of the length of the integer x.

Leave a Reply

Your email address will not be published. Required fields are marked *