Reverse Integer

Problem

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Solution

Construction from Tail Solution: O(lg n) time, O(1) space

public class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int tail = x % 10;
            int newRes = res * 10 + tail; //We must have a new var here to check overflow
            if ((newRes - tail) / 10 != res) return 0;
            res = newRes;
            x /= 10;
        }
        return res;
    }
}

Analysis

We use calculation to construct the reversed number of given x
As long as x != 0 we first get the tail by % and then construct the newRes
We calculate res from newRes to check overflow
At the end, we set res = newRes and move x to next digit