7. Reverse Integer

Description of the Problem

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints: -2^31 <= x <= 2^31 - 1

Solution

Explanation

Method 1: Use standard library to convert integer

Method 2: Do the Method by yourself. First perform checking of overflow/underflow. Then reverse the integer.

Checking of Overflow/Underflow

If a reverse integer overflows (or underflows), then it has at least 10 digits. (Since i32::MAX and i32::MIN has 10 digits). By contraposition, any number has less than 10 digits does not overflows (nor underflows).

To check whether a reversed full-digit integer overflows (or underflows), we can compare the number with i32::MAX or i32::MIN digit-by-digit.

Example 1: reverse of 2091748912 is 2198471902. Compare the reversed with i32::MAX digit-by-digit

2198471902
2147483647
-----------
1st digit: they are equal (i.e. 2) ==> compare next digit
2nd digit: they are equal (i.e. 1) ==> compare next digit
3nd digit: 9 > 4 ==> It overflows

Example 2: reverse of 2091748012 is 2108471902. Compare the reversed with i32::MAX digit-by-digit

2108471902
2147483647
-----------
1st digit: they are equal (i.e. 2) ==> compare next digit
2nd digit: they are equal (i.e. 1) ==> compare next digit
3nd digit: 0 < 4 ==> It is not possible to overflow

After the checking, just simply calculate the reversed value.

Code - Method 1 (Rust)

impl Solution {
    pub fn reverse(n: i32) -> i32 {
        let result = 
        if n > 0 {
            n.to_string() // convert the number into String
            .chars().rev() // reverse the number_string
            .collect::<String>() 
            .parse::<i32>() // try to parse the reversed number_string
        }
        else{
            n.to_string() // convert the number into String
            .chars().skip(1) // skip 1st character i.e. minus sign
            .collect::<String>() // convert it into String due to its type
            .chars().rev() // reverse the number_string
            .collect::<String>()
            .parse::<i32>() // try to parse the reversed number_string
            .map(|x| -x)
        };

        // Unwrap the result
        return if let Ok(x) = result{
            x
        }
        else{
            0
        };
    }
}

Code - Method 2 (Rust)

impl Solution {

    pub fn reverse(n: i32) -> i32 {
        static MAX_POW : u32 = 9; // std::i32::MAX and std::i32::MIN has 10 digits
        static TEN : i32 = 10;
        if Solution::will_overflow_or_underflow(n){
            return 0;
        }

        // Calculate the sum
        let mut sum = 0;
        let mut n = n;
        while n != 0 {
            sum *= 10;
            sum += n % 10;
            n /= 10;
        }

        return sum;
    }

    fn will_overflow_or_underflow(n : i32) -> bool {
        static MAX_POW : u32 = 9;
        static TEN : i32 = 10;

        // if the number is not in full-digit, so is its reverse
        if ( n>= 0 && n < TEN.pow(MAX_POW)) || (n < 0 && n > -TEN.pow(MAX_POW)){
            return false;
        }

        // Otherwise, check whether the reverse will overflow
        let mut is_not_overflow = true;
        let mut is_continued;
        for p in 0..=MAX_POW{
            let digit_n = n / TEN.pow(p) % 10;
            if n >= 0{
                let digit_max = std::i32::MAX / TEN.pow(MAX_POW - p) % 10;
                is_not_overflow = digit_n <= digit_max;
                // If the digits are equal, then we have to check next digits
                // Otherwise, its reverse must be smaller than std::i32::MAX
                is_continued = is_not_overflow && digit_n == digit_max;
            }else{
                let digit_min = std::i32::MIN / TEN.pow(MAX_POW - p) % 10;
                is_not_overflow = digit_n >= digit_min;
                // Similarly, if the digits are equal, then we have to check next digits
                // Otherwise, its reverse must be smaller than std::i32::MIN
                is_continued = is_not_overflow && digit_n == digit_min;
            }

            if !is_continued{break;}
        }
        return !is_not_overflow;
    }
}

Complexity - Method 2 (\(d\) is the number of digits)

Time complexity:

\( T(n) = O(2d) \)
- Perform Overflow/Underflow checking and Calculate the reversed number

Auxiliary Space:

\( S(n) = O(1) \)
- Extracted digits are stored in local variables

Leetbook