Reverse Integer

I’m doing some algorithm practice to improve my programming skills and to keep myself sharp. It’s really refreshing for an engineer like me who is so busy with day-to-day tasks which doesn’t require much of sophisticated algorithms though my job involves coding for automation.

In this article, I’m going to reverse integers. For example, if you receive 12345 and then function must return 54321. The function must handle the case where if the result overflows the integer max or min value.

I initially came up with a way to get absolute value, convert it to a string, reverse it and if the original value is negative, insert “-” to the index 0 of the string. Finally if you parse the string to integer, you get the result. This is not an ideal solution for several reasons. Here is the code.

    public void testPoorReverseInteger()
    {
        int reversed = poorReverseInteger(12345);
        System.out.println(reversed);
        assertEquals(reversed, 54321);

        reversed = poorReverseInteger(-12345);
        System.out.println(reversed);
        assertEquals(reversed, -54321);
    }

    private int poorReverseInteger(int input)
    {
        StringBuilder s = new StringBuilder(Integer.toString(Math.abs(input)));
        s = s.reverse();
        int result = 0;

        if (input < 0)
            s.insert(0, "-");

        try
        {
            result = Integer.parseInt(s.toString());
        }
        catch(NumberFormatException exp)
        {
            System.out.println(exp.toString());
            return 0;
        }

        return result;
    }

I think the time complexity is probably O(n) but the space complexity is O(2n). I’m also using exception for handling overflow situation and using exception for validation is relatively expensive. If you expect the exception to happen very often, the time complexity will add up. Also converting from integer to string and string back to integer is also not such an efficient process.

Here is another smarter way to reverse an integer.

    public void testReverseInteger()
    {
        int input = -12345456;
        int result = reverseInteger(input);
        System.out.println(result);
        assertEquals(result, -65454321);
    }

    private int reverseInteger(int input)
    {
        //max integer 2147483647
        //min integer -2147483648
        int result = 0;
        while (input != 0) {
            int lastDigit = input % 10;
            input /= 10;

            if (result > Integer.MAX_VALUE/10 || (result == Integer.MAX_VALUE/10 && lastDigit > 7))
            {
                return 0;
            }

            if (result < Integer.MIN_VALUE/10 || (result == Integer.MIN_VALUE/10 && lastDigit < -8))
            {
                return 0;
            }

            result = result * 10 + lastDigit;
        }

        return result;
    }

Declaring int result = 0; is no brainer. We will use it to keep the result for returning the value.

The logic of the function is to get the value of the last digit (line# 15) by getting a remainder of division by 10, reduce the value of input by dividing it by 10, check the overflow situation (from line# 18 to 26) and add it to the result variable. So for the first iteration of 12345, the last digit is 5. When 12345 is divided by 10, the value is reduced to 1234 because the variable is integer. The decimal point is omitted. Then in the next iteration, 4 is contained in the last digit. The result variable contains 5 at the point of hitting the line# 28, 5*10 + 4 = 54. If you repeat this process until input is 0, you will get 54321.

Let’s talk about handling the overflow situation.

if (result > Integer.MAX_VALUE/10 || (result == Integer.MAX_VALUE/10 && lastDigit > 7))

If the value of result variable is greater than the value of 1/10 of the max integer value, the result will be definitely larger than the max integer value, so there will be a overflow situation on line# 28.

Another situation that needs to handle is if the value of result variable is equals to the 1/10 of the max integer value and the last digit is larger than 7. The value of max integer is 2147483647 so if the value of lastDigit variable is greater than 7, the result will be greater than 2147483647. The validation for the min integer value is the same idea.

The latter method is better in a sense that the space complexity is O(n) but the time complexity is O(1) because it only deals with integer which is limited to 32 bit data. It also doesn’t depend on exception for overflow validation.

Recap

Knowing the nature of the data you are dealing with makes it more efficient to work with it. I’m planning to have more fun with algorithm especially in Java.

Author: admin

A software engineer in greater Seattle area

Leave a Reply

Your email address will not be published. Required fields are marked *