Code Implementation

class Solution:
    def reverse(self, x: int) -> int:
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        res = 0
        neg = x < 0
        x = abs(x)
        while x != 0:
            pop = x % 10
            x //= 10
            if res > INT_MAX // 10 or (res == INT_MAX // 10 and pop > 7):
                return 0
            res = res * 10 + pop
        return -res if neg else res
      

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (res > INT_MAX/10 || (res == INT_MAX/10 && pop > 7)) return 0;
            if (res < INT_MIN/10 || (res == INT_MIN/10 && pop < -8)) return 0;
            res = res * 10 + pop;
        }
        return res;
    }
};
      

class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE/10 && pop > 7)) return 0;
            if (res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE/10 && pop < -8)) return 0;
            res = res * 10 + pop;
        }
        return res;
    }
}
      

var reverse = function(x) {
    let res = 0;
    let neg = x < 0;
    x = Math.abs(x);
    while (x != 0) {
        let pop = x % 10;
        x = Math.floor(x / 10);
        if (res > Math.floor((2**31 - 1) / 10) || (res === Math.floor((2**31 - 1) / 10) && pop > 7)) {
            return 0;
        }
        res = res * 10 + pop;
    }
    res = neg ? -res : res;
    if (res < -(2**31) || res > 2**31 - 1) return 0;
    return res;
};
      

Problem Description

Given a signed 32-bit integer x, reverse its digits. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

• Assume the environment does not allow you to store 64-bit integers (such as long in Java).
• Negative numbers should remain negative after reversal.
• Leading zeros in the reversed number should be dropped (e.g., 120 becomes 21).
• The function signature is typically reverse(int x) or equivalent.

Thought Process

At first glance, reversing an integer seems simple: convert the number to a string, reverse it, and convert it back. However, we must handle negative numbers, ignore leading zeros, and most importantly, watch for integer overflow.

A brute-force approach would use string conversion, but this is not ideal for interviews or for handling the overflow constraint. Instead, we want to process the number digit by digit, building the reversed integer mathematically, and checking for overflow before it happens.

The main challenge is to avoid exceeding the 32-bit integer limits during reversal. We must check before each step if multiplying the current result by 10 and adding the next digit would overflow.

Solution Approach

Let's break down the optimal approach step by step:

1. Extract digits one by one:
   • Use modulo (%) to get the last digit (pop = x % 10).
   • Remove the last digit from x by integer division (x //= 10 or x /= 10).
2. Build the reversed number:
   • Multiply the current result by 10 and add pop (res = res * 10 + pop).
3. Check for overflow before each step:
   • Before updating res, check if it will overflow:
     • If res > INT_MAX // 10 or res == INT_MAX // 10 and pop > 7, return 0.
     • For negatives: If res < INT_MIN // 10 or res == INT_MIN // 10 and pop < -8, return 0.
     • These constants come from the maximum and minimum values for 32-bit signed integers.
4. Handle sign:
   • Process the number as a positive integer, store the sign, and apply it at the end.
5. Return the result:
   • If no overflow occurred, return the reversed integer with the correct sign.

Example Walkthrough

Let's take x = 123 as an example:

• First iteration:
  • pop = 123 % 10 = 3
  • x = 123 // 10 = 12
  • res = 0 * 10 + 3 = 3
• Second iteration:
  • pop = 12 % 10 = 2
  • x = 12 // 10 = 1
  • res = 3 * 10 + 2 = 32
• Third iteration:
  • pop = 1 % 10 = 1
  • x = 1 // 10 = 0
  • res = 32 * 10 + 1 = 321
• Done: x is now 0, so we return 321.

For a negative input, e.g., x = -120, we keep track of the sign, process 120 as above, and return -21.

For an input like 1534236469, reversing would cause overflow, so the function returns 0.

Time and Space Complexity

• Brute-force (string conversion):
  • Time: O(k), where k is the number of digits in x.
  • Space: O(k), for the string representation.
• Optimized (digit-by-digit):
  • Time: O(k), since we process each digit once.
  • Space: O(1), as we only use a few variables, not extra data structures.

The optimized approach is both faster (no string manipulation) and more space-efficient.

Summary

The Reverse Integer problem is a classic example of careful digit manipulation and overflow checking. By extracting digits one by one and building the result mathematically, we avoid string conversions and ensure efficiency. The critical insight is to check for overflow before it happens, making the solution robust and suitable for interviews. The approach is concise, efficient, and highlights the importance of understanding integer limits in programming.