9. Palindrome Number

Description

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:

-2³¹ <= x <= 2³¹ - 1

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

Solutions

Solution 1: Reverse Half of the Number

First, we determine special cases:

If \(x < 0\), then \(x\) is not a palindrome, directly return false;
If \(x > 0\) and the last digit of \(x\) is \(0\), then \(x\) is not a palindrome, directly return false;
If the last digit of \(x\) is not \(0\), then \(x\) might be a palindrome, continue the following steps.

We reverse the second half of \(x\) and compare it with the first half. If they are equal, then \(x\) is a palindrome, otherwise, \(x\) is not a palindrome.

For example, for \(x = 1221\), we can reverse the second half from "21" to "12" and compare it with the first half "12". Since they are equal, we know that \(x\) is a palindrome.

Let's see how to reverse the second half.

For the number \(1221\), if we perform \(1221 \bmod 10\), we will get the last digit \(1\). To get the second last digit, we can first remove the last digit from \(1221\) by dividing by \(10\), \(1221 / 10 = 122\), then get the remainder of the previous result divided by \(10\), \(122 \bmod 10 = 2\), to get the second last digit.

If we continue this process, we will get more reversed digits.

By continuously multiplying the last digit to the variable \(y\), we can get the number in reverse order.

In the code implementation, we can repeatedly "take out" the last digit of \(x\) and "add" it to the end of \(y\), loop until \(y \ge x\). If at this time \(x = y\), or \(x = y / 10\), then \(x\) is a palindrome.

The time complexity is \(O(\log_{10}(n))\), where \(n\) is \(x\). For each iteration, we will divide the input by \(10\), so the time complexity is \(O(\log_{10}(n))\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRustJavaScriptC#PHP

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)

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;
    }
}

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;
    }
};

func isPalindrome(x int) bool {
    if x < 0 || (x > 0 && x%10 == 0) {
        return false
    }
    y := 0
    for ; y < x; x /= 10 {
        y = y*10 + x%10
    }
    return x == y || x == y/10
}

function isPalindrome(x: number): boolean {
    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);
}

impl Solution {
    pub fn is_palindrome(mut x: i32) -> bool {
        if x < 0 || (x != 0 && x % 10 == 0) {
            return false;
        }
        let mut y = 0;
        while x > y {
            y = y * 10 + x % 10;
            x /= 10;
        }
        x == y || x == y / 10
    }
}

/**
 * @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);
};

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;
    }
}

class Solution {
    /**
     * @param Integer $x
     * @return Boolean
     */
    function isPalindrome($x) {
        if ($x < 0 || ($x && $x % 10 == 0)) {
            return false;
        }
        $y = 0;
        while ($x > $y) {
            $y = $y * 10 + ($x % 10);
            $x = (int) ($x / 10);
        }
        return $x == $y || $x == (int) ($y / 10);
    }
}

9. Palindrome Number

Description

Solutions

Solution 1: Reverse Half of the Number

Comments