Reverse Integer

Leet code Link - https://leetcode.com/problems/reverse-integer/description/

Complexity - Medium

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 [-231, 231 - 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:

-231 <= x <= 231 - 1

Solution

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

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

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 temp=rev⋅10+pop can cause overflow.

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

To explain, lets assume that rev is positive.

If temp=rev⋅10+pop causes overflow, then it must be that rev≥ 10 INTMAX ​

If rev> 10 INTMAX ​ , then temp=rev⋅10+pop is guaranteed to overflow. If rev== 10 INTMAX ​ , then temp=rev⋅10+pop will overflow if and only if pop>7 Similar logic can be applied when rev is negative.Reversing an integer can be done similarly to reversing a string.

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

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 temp=rev⋅10+pop can cause overflow.

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

To explain, lets assume that rev is positive.

If temp=rev⋅10+pop causes overflow, then it must be that rev≥ 10 INTMAX ​

If rev> 10 INTMAX ​ , then temp=rev⋅10+pop is guaranteed to overflow. If rev== 10 INTMAX ​ , then temp=rev⋅10+pop will overflow if and only if pop>7 Similar logic can be applied when rev is negative.

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

Time Complexity: O(log(x)). There are roughly log 10 ​ (x) digits in x.

Space Complexity: O(1).