LeetCode (Algorithms#7) ‒ Reverse Integer

Problem

Reverse digits of an integer.

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

Examples:

x = 123, return 321
x = -123, return -321

Solution

The solution is pretty straightforward. We want to iterate through the numbers and add each one to a new number after shifting it to the correct position, while checking if the addition would cause an overflow. With the number assumed to be an int, this can be done in a hackish way by using a long, and comparing to the max int values. This problem is a good example of one that can be optimized after a naive implementation.

I personally started this problem by directly translating the approach into code. How do you know how far to shift each number over? Compute the length of the number first, iterate through it, isolate each digit, then shift and add it.

public int reverse(int x) {
    int n = 0, res = 0;
    for (int _x=x; _x!=0; _x/=10) n++; // count digits
    long k;
    for (int i=1; i<=n; i++) {
        k = x % (int)Math.pow(10,i) / (int)Math.pow(10,i-1); // isolate ith digit
        long q = k*(long)Math.pow(10,n-i); // shift digit over
        if (q+(long)res<Integer.MIN_VALUE || q+(long)res>Integer.MAX_VALUE) return 0; 
        res += (int)q;
    }
    return res;
}

Naturally, we'd first want to try and combine this into a single loop. This can be done by shifting the whole reversed number each iteration, instead of fully shifting each number in each iteration (which requires n):

public int reverse(int x) {
    long k, _x=x, res = 0;
    for (int i=1; _x!=0; i++) {
        k = x % (int)Math.pow(10,i) / (int)Math.pow(10,i-1);
        res *= 10;
        res += k;
        _x /= 10;
        if (res<Integer.MIN_VALUE || res>Integer.MAX_VALUE) return 0; 
    }
    return (int)res;
}

The problem with this code is that the calls to Math.pow() do not run in constant time, and so the algorithm does no run in the O(n) time complexity that is expect. These can be eliminated by noticing that while shifting the original digits right (to determine when there are no more digits), we can take the first digit (by modding it with 10), and add it to the reversed number, which is being shifted left at the same time. This produces the more concise code below.

Time complexity: O(n)
Space complexity: O(n)
Runtime percentile: 72.56%

public int reverse(int x) {
    long _x=x, res = 0;
    while (_x!=0) {
        res = res*10 + _x%10;
        _x /= 10;
        if (res<Integer.MIN_VALUE || res>Integer.MAX_VALUE) return 0; 
    }
    return (int)res;
}

(Another less elegant solution is to simply convert it to a string, reverse the string, and convert it back to an int)