ash0x0's Obsidian Quartz

9. Palindrome Number

4 min read

Problem

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

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.

Constraints:

  • -231 <= x <= 231 - 1

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

Solution

Two Pointer - O(n) time - O(n) space

Convert integer to string and use the pointers to match items from the end with items from the beginning

#include<string>
 
using namespace std;
 
class Solution {
public:
    bool isPalindrome(int x) {
        string number = to_string(x);
        for (int i = 0, j = number.size() - 1;
            i < j, j > i;
            i++, j--) {
                if (number[i] != number[j]) return false;
            }
        return true;
    }
};

Revert half the number - O(n) time - O(1) space

Second idea would be reverting the number itself, and then compare the number with original number, if they are the same, then the number is a palindrome.

However, if the reversed number is larger than INT_MAX, we will hit integer overflow. To avoid the overflow issue of the reverted number, what if we only revert half of the int number? The reverse of the last half of the palindrome should be the same as the first half of the number, if the number is a palindrome.

For example, if the input is 1221, if we can revert the last part of the number “1221” from “21” to “12”, and compare it with the first half of the number “12”, since 12 is the same as 12, we know that the number is a palindrome.

First of all we should take care of an edge case:

  1. All negative numbers are not palindrome, for example: -123 is not a palindrome since the ’-’ does not equal to ‘3’. So we can return false for all negative numbers.

For number 1221, if we do 1221 % 10, we get the last digit 1, to get the second to the last digit, we need to remove the last digit from 1221, we could do so by dividing it by 10 1221 / 10 = 122.

Then we can get the last digit again by doing a modulus by 10, 122 % 10 = 2, and if we multiply the last digit by 10 and add the second last digit, 1 * 10 + 2 = 12, it gives us the reverted number we want. Continuing this process would give us the reverted number with more digits.

How do we know that we’ve reached the half of the number?

Since we divided the number by 10, and multiplied the reversed number by 10, when the original number is less than the reversed number, it means we’ve processed half of the number digits.

class Solution {
public:
    bool isPalindrome(int x) {
        // Special cases:
        // As discussed above, when x < 0, x is not a palindrome.
        // Also if the last digit of the number is 0, in order to be a
        // palindrome, the first digit of the number also needs to be 0. Only 0
        // satisfy this property.
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
 
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
 
        // When the length is an odd number, we can get rid of the middle digit
        // by revertedNumber/10 For example when the input is 12321, at the end
        // of the while loop we get x = 12, revertedNumber = 123, since the
        // middle digit doesn't matter in palidrome(it will always equal to
        // itself), we can simply get rid of it.
        return x == revertedNumber || x == revertedNumber / 10;
    }
};

Graph View