# Palindrome Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/palindrome-number)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cognizant](https://scaleengineer.com/companies/cognizant), [Deloitte](https://scaleengineer.com/companies/deloitte), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [FPT](https://scaleengineer.com/companies/fpt), [Garmin](https://scaleengineer.com/companies/garmin), [HCL](https://scaleengineer.com/companies/hcl), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Samsung](https://scaleengineer.com/companies/samsung), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Roche](https://scaleengineer.com/companies/roche)
---
## 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:**

* `-231 <= x <= 231 - 1`

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

# Approaches
## Convert to String and Compare
The most intuitive approach is to convert the integer into a string. Once we have the string representation, we can easily check if it's a palindrome. This can be done by comparing the string with its reversed version or by using a two-pointer technique.
**Time:** O(d), where d is the number of digits in x. Converting the number to a string takes O(d) time, and the two-pointer comparison also takes O(d) time. · **Space:** O(d), for storing the string representation of the number, where d is the number of digits.
**Pros:** Very simple and easy to understand.; Leverages built-in string manipulation functionalities.
**Cons:** Requires extra space proportional to the number of digits to store the string.; Does not meet the 'follow-up' constraint of solving it without string conversion.
### Explanation
First, we handle the edge case: negative numbers are not palindromes, so if `x` is less than 0, we return `false` immediately.
Next, we convert the integer `x` into its string representation, let's call it `s`.
We then use two pointers, `left` starting at the beginning of the string (index 0) and `right` starting at the end (index `s.length() - 1`).
We iterate as long as `left` is less than `right`, comparing the characters at these two pointers. If at any point `s.charAt(left)` does not equal `s.charAt(right)`, we know it's not a palindrome and can return `false`.
In each iteration, we move the pointers closer to the center by incrementing `left` and decrementing `right`.
If the loop completes without finding any mismatches, it means the string is a palindrome, and we return `true`.
```java
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        String s = Integer.toString(x);
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
1. Check if the input integer `x` is negative. If it is, return `false`.
2. Convert the integer `x` to a string `s`.
3. Initialize two pointers: `left = 0` and `right = s.length() - 1`.
4. Loop while `left < right`:
   a. If the character at `left` is not equal to the character at `right`, return `false`.
   b. Increment `left` and decrement `right`.
5. If the loop finishes, the number is a palindrome, so return `true`.

## Revert the Whole Number Mathematically
This approach avoids string conversion by mathematically reversing the entire integer. We then compare the reversed integer with the original one. If they are identical, the number is a palindrome.
**Time:** O(d), where d is the number of digits in x. We iterate through each digit of the number once. · **Space:** O(1), as we only use a few variables to store the numbers, regardless of the input size.
**Pros:** Solves the problem without using extra space that depends on input size (O(1) space).; Adheres to the 'follow-up' constraint.
**Cons:** The reversed number can potentially overflow the standard integer type, requiring the use of a larger data type like `long` for the reversed number.
### Explanation
As with the first approach, we first handle the edge case of negative numbers, which are never palindromes.
We need to keep a copy of the original number, `originalX`, for the final comparison.
We then proceed to reverse the number. We initialize a variable `reversedNum` to 0. We repeatedly take the last digit of our current number (`x % 10`), add it to `reversedNum` after multiplying `reversedNum` by 10, and then remove the last digit from `x` (`x / 10`).
A critical consideration is potential integer overflow. If the reversed number becomes larger than `Integer.MAX_VALUE`, it will wrap around and give an incorrect result. To prevent this, we can declare `reversedNum` as a `long`.
After the loop finishes (when `x` becomes 0), we compare `reversedNum` with `originalX`. If they are equal, the number is a palindrome.
```java
class Solution {
    public boolean isPalindrome(int x) {
        // Negative numbers are not palindromes
        if (x < 0) {
            return false;
        }

        long reversedNum = 0;
        int originalX = x;

        while (x != 0) {
            int digit = x % 10;
            reversedNum = reversedNum * 10 + digit;
            x = x / 10;
        }

        return originalX == reversedNum;
    }
}
```
### Algorithm
1. If `x` is negative, return `false`.
2. Store the original value of `x` in a variable, e.g., `originalX`.
3. Initialize a `long` variable `reversedNum = 0` to store the reversed number and prevent overflow.
4. Loop while `x` is not 0:
   a. Get the last digit: `digit = x % 10`.
   b. Append the digit to the reversed number: `reversedNum = reversedNum * 10 + digit`.
   c. Remove the last digit from `x`: `x = x / 10`.
5. Compare `originalX` with `reversedNum`. If they are equal, return `true`; otherwise, return `false`.

## Revert Half the Number
This is the most optimal approach. Instead of reversing the entire number (which risks overflow), we only reverse the second half. We then compare the first half of the original number with the reversed second half. This avoids the overflow problem and is slightly more efficient.
**Time:** O(log10(n)) or O(d), where d is the number of digits. More precisely, it's O(d/2) as it only iterates through half the digits. · **Space:** O(1), as it uses a constant amount of extra space.
**Pros:** Most efficient in terms of both time and space.; Avoids the integer overflow problem completely without needing a `long`.; Processes only half of the digits of the number.
**Cons:** The logic, especially the final comparison for odd/even length numbers, can be slightly less intuitive at first glance.
### Explanation
First, we handle some edge cases that can be identified quickly. Negative numbers are not palindromes. Also, any number that ends in 0 (except for 0 itself) cannot be a palindrome (e.g., 10, 120), because a non-zero number cannot start with 0. So, if `x < 0` or `(x % 10 == 0 && x != 0)`, we return `false`.
We initialize a variable `revertedNumber = 0`. We then enter a loop that continues as long as `x` is greater than `revertedNumber`.
Inside the loop, we build up `revertedNumber` by taking the last digit of `x` and appending it. Simultaneously, we shrink `x` by removing its last digit. This process effectively moves digits from the end of `x` to the end of `revertedNumber`.
The loop stops when we've processed half of the digits. At this point, `x` holds the first half of the number, and `revertedNumber` holds the reversed second half.
Finally, we check for palindrome property:
   - If the original number has an even number of digits (e.g., 1221), the loop stops when `x` is 12 and `revertedNumber` is also 12. So, we check if `x == revertedNumber`.
   - If the original number has an odd number of digits (e.g., 12321), the loop stops when `x` is 12 and `revertedNumber` is 123. The middle digit '3' is irrelevant for the palindrome check. We can discard it by dividing `revertedNumber` by 10. So, we check if `x == revertedNumber / 10`.
Combining these two conditions, we return `true` if `x == revertedNumber || x == revertedNumber / 10`.
```java
class Solution {
    public boolean isPalindrome(int x) {
        // Edge cases:
        // 1. Negative numbers are not palindromes.
        // 2. If the last digit is 0, to be a palindrome, the first digit must also be 0.
        //    Only 0 itself fits this condition.
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // For numbers with an odd number of digits, we can get rid of the middle digit
        // by revertedNumber/10. For example, when x = 12321, at the end of the while loop
        // we get x = 12, revertedNumber = 123.
        // Since the middle digit doesn't matter in a palindrome, we can simply divide it out.
        return x == revertedNumber || x == revertedNumber / 10;
    }
}
```
### Algorithm
1. Handle edge cases: If `x` is negative, or if `x` ends in 0 but is not 0 itself, return `false`.
2. Initialize `revertedNumber = 0`.
3. Loop while `x > revertedNumber`:
   a. Update `revertedNumber`: `revertedNumber = revertedNumber * 10 + x % 10`.
   b. Update `x`: `x = x / 10`.
4. After the loop, compare the first half (`x`) with the reversed second half (`revertedNumber`).
   - For an even number of digits, `x` will be equal to `revertedNumber`.
   - For an odd number of digits, the middle digit will be on `revertedNumber`, so we compare `x` with `revertedNumber / 10`.
5. Return `x == revertedNumber || x == revertedNumber / 10`.

# Solutions
### CSharp

```csharp
public class Solution { public bool IsPalindrome ( int x ) { if ( x < 0 || ( x > 0 && x % 10 == 0 )) { return false ; } int y = 0 ; for (; y < x ; x /= 10 ) { y = y * 10 + x % 10 ; } return x == y || x == y / 10 ; } }
```

### Java

```java
class Solution {
public
  boolean isPalindrome(int x) {
    if (x < 0 || (x > 0 && x % 10 == 0)) {
      return false;
    }
    int y = 0;
    for (; y < x; x /= 10) {
      y = y * 10 + x % 10;
    }
    return x == y || x == y / 10;
  }
}

```

### JavaScript

```javascript
/** * @param {number} x * @return {boolean} */ var isPalindrome = function (x) {
  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);
};

```

### CPP

```cpp
class Solution {
public:
  bool isPalindrome(int x) {
    if (x < 0 || (x && x % 10 == 0)) {
      return false;
    }
    int y = 0;
    for (; y < x; x /= 10) {
      y = y * 10 + x % 10;
    }
    return x == y || x == y / 10;
  }
};

```

### Python

```python
class Solution:
    def isPalindrome(self, x: int) -> bool: if x < 0 or (x and x % 10 == 0): return False y = 0 while y < x: y = y * 10 + x % 10 x //= 10 return x in (y, y // 10)

```