Reverse Integer

Problem Description

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³¹, 2³¹ - 1], then return 0.

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

Examples

Constraints

• -2³¹ ≤ x ≤ 2³¹ - 1

Prevent Overflow Before It Happens

The standard digit reversal loop:

1. pop = x % 10
2. x /= 10
3. rev = rev * 10 + pop

To prevent overflow before multiplying by 10 (since the environment forbids 64-bit integers like long that could hold the overflowed value):

• For positive values, we overflow if rev > INT_MAX / 10, or if rev == INT_MAX / 10 and pop > 7 (since 2³¹ - 1 = 2147483647).
• For negative values, we overflow if rev < INT_MIN / 10, or if rev == INT_MIN / 10 and pop < -8 (since -2³¹ = -2147483648).

Solution: Bounds Pruning

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;

            // positive overflow check
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            // negative overflow check
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }

            rev = rev * 10 + pop;
        }
        return rev;
    }
}

class Solution:
    def reverse(self, x: int) -> int:
        # Python integers have arbitrary precision, but we must simulate 32-bit limits
        INT_MIN, INT_MAX = -2**31, 2**31 - 1
        
        # track sign
        sign = -1 if x < 0 else 1
        x = abs(x)
        
        rev = 0
        while x != 0:
            pop = x % 10
            x //= 10
            
            # check overflow bounds
            if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
                return 0
                
            rev = rev * 10 + pop
            
        return sign * rev

#include <climits>

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;

            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8)) return 0;

            rev = rev * 10 + pop;
        }
        return rev;
    }
};

Complexity Analysis:

• Time Complexity: O(log₁₀ X) where X is the value of x. The loop runs once per digit (at most 10 digits for 32-bit integers).
• Space Complexity: O(1).

← All Problems