Reverse Integer

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

Approach 1: Pop and Push Digits with Overflow Check

The key insight is to extract digits from the end and build the reversed number, checking for overflow before each operation.

Implementation

class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        result = 0
        sign = 1 if x > 0 else -1
        x = abs(x)

        while x:
            # Extract last digit
            digit = x % 10
            x //= 10

            # Check for overflow before updating result
            if result > INT_MAX // 10:
                return 0
            if result == INT_MAX // 10 and digit > INT_MAX % 10:
                return 0

            result = result * 10 + digit

        return sign * result

Approach 2: Using String Conversion

class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        # Handle sign
        sign = 1 if x >= 0 else -1
        x = abs(x)

        # Reverse digits using string
        reversed_str = str(x)[::-1]
        result = sign * int(reversed_str)

        # Check overflow
        if result < INT_MIN or result > INT_MAX:
            return 0

        return result

Approach 3: With Early Overflow Detection

class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        result = 0

        while x != 0:
            # Extract last digit (handle negative numbers)
            digit = int(x % 10) if x > 0 else int(x % -10)
            x = int(x / 10)  # Truncate towards zero

            # Check overflow before multiplying by 10
            if result > INT_MAX // 10 or (result == INT_MAX // 10 and digit > 7):
                return 0
            if result < INT_MIN // 10 or (result == INT_MIN // 10 and digit < -8):
                return 0

            result = result * 10 + digit

        return result

Approach 4: Simplified with Python Features

class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        # Use string reversal
        s = str(x)
        if s[0] == '-':
            result = -int(s[-1:0:-1])
        else:
            result = int(s[::-1])

        # Check bounds
        return result if INT_MIN <= result <= INT_MAX else 0

Complexity Analysis

Time Complexity: O(log x), where x is the input number. We process each digit once, and number of digits is log₁₀(x).
Space Complexity: O(1) for math approach, O(log x) for string approach.

Key Insights

Digit Extraction: Use x % 10 to get last digit, x // 10 to remove it.
Building Reversed Number: Multiply current result by 10 and add new digit: result = result * 10 + digit
Overflow Detection: Check if result > INT_MAX // 10 before multiplying by 10 to avoid overflow.
Edge Case - Exact Boundary: When result == INT_MAX // 10, also check if next digit would cause overflow.
Sign Handling: Can work with absolute value and apply sign at end, or handle negative numbers throughout.
32-bit Limits:
- INT_MAX = 2,147,483,647 (2³¹ - 1)
- INT_MIN = -2,147,483,648 (-2³¹)
Trailing Zeros: Reversed number loses leading zeros (120 → 21).
String Method Trade-off: String reversal is simpler but uses O(log x) space and may not satisfy “no 64-bit” constraint literally.