Solution


Approach 1: Pop and Push Digits & Check before Overflow

Intuition

We can build up the reverse integer one digit at a time. While doing so, we can check beforehand whether or not appending another digit would cause overflow.

Algorithm

Reversing an integer can be done similarly to reversing a string.

We want to repeatedly "pop" the last digit off of and "push" it to the back of the . In the end, will be the reverse of the .

To "pop" and "push" digits without the help of some auxiliary stack/array, we can use math.

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

However, this approach is dangerous, because the statement can cause overflow.

Luckily, it is easy to check beforehand whether or this statement would cause an overflow.

To explain, lets assume that is positive.

  1. If causes overflow, then it must be that
  2. If , then is guaranteed to overflow.
  3. If , then will overflow if and only if

Similar logic can be applied when is negative.

Complexity Analysis

  • Time Complexity: . There are roughly digits in .
  • Space Complexity: .