Leetcode: Reverse Integer

Reverse digits of an integer.

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

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Understand the problem:
The problem asks for reversing an integer. As suggested by the problem, there are several cases need to consider.

• For an positive number, .e.g. 123, return 321
• For a negative number, e.g. -123, return -321
• For an integer ends with 0, e.g. 1230, return 321. 
• Handle the reverse integer is overflowed. E.g. the Integer.MAX_VALUE, 2147483648, the reverse number is overflowed. One possible way is to use a long int to store the number, if it is overflowed, return the MAX_VALUE or MIN_VALUE, else cast back to integer. 

Solution:
The basic idea is to firstly parse the integer into digits and store them. We parse it from right to left, according to  the post of "convert string into integer". So for integer 123, the parsed digits would be 321. If there are leading zeros, we ignore it. Then we convert the digits into an integer, stored in the long format. 

Code (Java):

public class Solution {
    public int reverse(int x) {
        if (x < 10 && x > -10) return x;
        
        ArrayList<Integer> buf = new ArrayList<Integer>();
        boolean neg = false;
        long result = 0;
        
        // if x is negative, we turn it to postive in temporary
        if (x < 0) {
            neg = true;
            x = -x;
        }
        
        // parse the integer into digits and store into the buf
        while (x > 0) {
            int temp = x % 10;
            buf.add(temp);
            x /= 10;
        }
        
        // remove leading zeros
        int start = 0;
        for (int i = 0; i < buf.size(); i++) {
            if (buf.get(i) != 0) {
                start = i;
                break;
            }
        }
        
        // convert the digits back to reversed integer
        for (int i = start; i < buf.size(); i++) {
            result *= 10;
            result += buf.get(i);
        }
        
        // consider the negative value
        if (neg) result = -result;
        
        // handle the overflow
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        
        return (int)result;
    }
}

Discussion:
The code is correct but looks redundant. It need extra space to store the temporary string/list. 

A Better Solution:
A better way is when we get an integer from the end, we directly convert to the reverse integer. In this way we don't need to care about the leading zeros as well. 

Code (Java):

public class Solution {
    public int reverse(int x) {
        if (x < 10 && x > -10) return x;
        long result = 0;
        boolean neg = false;
        
        // consider the negative case
        if (x < 0) {
            neg = true;
            x= -x;
        }
        
        while (x > 0) {
            int digit = x % 10;
            x = x / 10;
            
            result = result * 10 + digit;
        }
        
        if (neg) result = -result;
        
        // handle the overflow issue
        if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        
        return (int) result;
    }
}

Summary:
This question is not difficult. But some take-away messages: 

• Handle each corner cases well, e.g. negative, leading zeros, integer overflow, etc..
• Convert integer to string, using %10,  and /10
• Convert string to integer, using *10