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^31 <= x <= 2^31 - 1

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

Solution

Explanation

In order to solve the problem without converting the integer to a string, we use numerical way to solve the problem.

If the number is negative, it can never be palindrome. If the number is positive, we can mirror the number to see whether it is equal to the original number.

Code (Rust)

impl Solution {
    // Numerical Way
    pub fn is_palindrome(x: i32) -> bool {
        if x < 0 {
            return false;
        }
        else{
            let mut sum = 0;
            let mut x_copy = x;

            while x_copy > 0{
                sum *= 10; // Sum shifts left by 1
                sum += x_copy % 10; // Extract digit
                x_copy /= 10; // x_copy shifts right by 1
            }
            return sum == x;
        }
    }
}

Complexity

n is the number of digits of input number

Time complexity:

\( T(n) = O(n) \)

Auxiliary Space:

\( S(n) = O(1) \)

Leetbook