Naive Solution

A naive approach would be to convert the integer to a string, reverse the string, and then convert the string back to an integer. However, we must handle the negative sign and the overflow/underflow cases.

def reverse_integer_naive(x):
    s = str(x)
    sign = -1 if s[0] == '-' else 1
    if sign == -1:
        s = s[1:]
    reversed_s = s[::-1]
    result = sign * int(reversed_s)
    
    if result < -2**31 or result > 2**31 - 1:
        return 0
    return result

• Time Complexity: O(N), where N is the number of digits in the integer.
• Space Complexity: O(N), for storing the string representation.

Optimal Solution

The optimal solution avoids using strings and performs the reversal using mathematical operations. We can extract the last digit using the modulo operator (%) and build the reversed number incrementally. We also need to check for overflow and underflow before updating the reversed number.

def reverse_integer_optimal(x):
    reversed_x = 0
    sign = 1 if x >= 0 else -1
    x = abs(x)
    
    while x > 0:
        pop = x % 10
        x //= 10

        # Check for overflow before multiplying
        if reversed_x > 2**31 // 10 or (reversed_x == 2**31 // 10 and pop > 7):
            return 0
        # Check for underflow before multiplying
        if reversed_x < (-2)**31 // 10 or (reversed_x == (-2)**31 // 10 and pop < -8):
            return 0

        reversed_x = reversed_x * 10 + pop

    return sign * reversed_x

• Time Complexity: O(log(N)), where N is the input number. This is because the number of iterations is proportional to the number of digits in the integer, and the number of digits is logarithmic with respect to the value of the integer.
• Space Complexity: O(1), as we are using only a constant amount of extra space.

Edge Cases

• Positive Integers: The algorithm should correctly reverse positive integers.
• Negative Integers: The algorithm should handle negative integers correctly by preserving the sign.
• Trailing Zeros: Trailing zeros should be removed when reversing (e.g., 120 becomes 21).
• Overflow: If the reversed number is outside the 32-bit signed integer range, return 0.
• Zero: If the input is zero, the output should be zero.