Data Structures And Algorithms

Reverse integer - C# solution for LeetCode problem

C# solution for the reverse integer LeetCode problem

The problem is simple - given a 32-bit integer A, return a 32-bit integer B which is A with all digits reversed. The detailed problem statement can be found at the LeetCode website. The solution is also trivial if you know basic Arithmetic and can wield it creatively. An important constraint mentioned is

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Solutions

Naive solution

The first goal is to arrive at a solution. I do not care about the aesthetics of it as long as it works for all inputs. I also do not care about the constraints.

The remainder operator of C# is a great way to extract the last digit of any given integer x. The remainder is the last digit when x is divided by 10.

int remainder = x % 10;

The remainder thus obtained is to be stored in a List<int>. Also, the following will give us the integer x, with its last digit removed

x = (x - remainder)/10;

With these two simple concepts sorted out, the bulk of the conceptual work is done. The algorithm to be followed is:

1. extract digits out of the input integer and store the digits in a List<int>
2. once all digits have been extracted and stored, get the stored digits and create an integer

The step 1 of the algorithm can be coded as

while(true)
{
	/* if during the process of truncating the input integer x,
     * it becomes smaller that 10 or in other words only the last
     * digit remains, add it to the list and break loop
     */
	if(x < 10)
    {
    	list.Add(x);
       	break;
	}
    int remainder = x % 10;
    /* this will remove the last digit from the input integer x.
     * the above step has already detected the last digit of x and
     * stored it in the "remainder" variable.
     */
    x = (x - remainder)/10;
    list.Add(remainder);
}

The step 2 of the algorithm can be coded as

double returnNumber = 0;
for(int i = 0; i < list.Count; i++)
{
	int item = list[i];
    if(item == 0)
    	continue;
    /* the digits stored in the list need to be multiplied by the appropriate
     * power of 10 to generate the output integer.
     * the first digit in the list is multiplied by 
     * 10 ^ (number of digits in x - 1), second digit is
     * multiplied by 10 ^ (number of digits in x - 1) and so on...
     */
    returnNumber += item * Math.Pow(10, list.Count - i - 1);
}

The complete implementation follows. The code has enough comments to explain what is going on:

public class Solution 
{
    public int Reverse(int x)
    {
        List<int> list = new List<int>();
        
        /* we need to keep track of the negativity :)
         * if we do not, we forget about it during the extraction of digits
         * while loop and also while creating the result integer 
         * in the for loop. The negativity will come back to bite us
         * when we return the result. */
        bool isNegative = x < 0 ? true : false;
        if(isNegative)
            x = x * -1;
        
        /* how does this loop work?
         * Example input = 123.
         * first iteration:
         * 		- is 123 < 10? No.
         * 		- remainder = 123 % 10 = 3
         *      - x = (123 - 3)/10 = 12
         *      - list.Add(3)
         * second iteration:
         * 		- is 12 < 10? No.
         * 		- remainder = 12 % 10 = 2
         *      - x = (12 - 2)/10 = 1
         *      - list.Add(2)
         * third iteration:
         * 		- is 1 < 10? Yes.
         *      - list.Add(1) and break */
        while(true)
        {
            /* x has had its negativity removed above. if we had not done
             * that this check would have let all negative x just pass
             * through and break the loop.
             *
             * why not Math.Abs(x)?
             * because it does not work for the following boundary value:
             * -2147483648 (Int32.MinValue)
             /* It throws a Runtime Error Message for -2147483648:
             Unhandled exception. System.OverflowException: Negating the
             minimum value of a twos complement number is invalid. */
            if(x < 10)
            {
                list.Add(x);
                break;
            }
            int remainder = x % 10;
            x = (x - remainder)/10;
            list.Add(remainder);
        }
        
        /* how does this loop work?
         * list = {3, 2, 1}
         * first iteration:
         * 		- returnNumber = 0 + 3 * Math.Pow(10, 3 - 0 - 1) = 300
         * second iteration:
         * 		- returnNumber = 300 + 2 * Math.Pow(10, 3 - 1 - 1) = 320
         * third iteration:
         * 		- returnNumber = 320 + 1 * Math.Pow(10, 3 - 2 - 1) = 321 */

        double returnNumber = 0;
        for(int i = 0; i < list.Count; i++)
        {
            int item = list[i];
            if(item == 0)
                continue;
            /* there is no power operator in C#. there is only
             * Math.Pow() and it only deals with doubles (not integers).
         	 * this is a blatant disregard of the following constraint:
             * Assume the environment does not allow you to store 64-bit
             * integers (signed or unsigned)
            returnNumber += item * Math.Pow(10, list.Count - i - 1);
        }
        
        /* Convert.ToInt32() throws an OverflowException when input larger
         * than Int32.MaxValue or Int32.MinValue.
         * the other option of casting does not alert in any way if the
         * conversion from double to integer fails.
         * in effect, OverflowException in Convert.ToInt32() is the only way
         * to know if the integer we generated as output is a valid one. */
        try
        {
            if(isNegative)
                Convert.ToInt32(returnNumber * -1);
            else
                Convert.ToInt32(returnNumber);
        }
        catch(Exception)
        {
            returnNumber = 0;
        }

        if(isNegative)
            return (int)returnNumber * -1;
        else
            return (int)returnNumber;
    }
}

Optimized solution

Analyzing the naive solution thoroughly we can easily see that the individual digits obtained by the application of remainder operator of C# need not be stored in a List<int>. Rather, an integer variable would suffice

/* replace */
int remainder = x % 10;
list.Add(remainder);
/* with */
returnNumber = returnNumber * 10 + x % 10;
/* to get rid of List<int> storage */

Also, the digit extraction can be trivially optimized. Maybe, the compiler does this. However, nothing wrong in being exact in the code itself rather than hoping the compiler will optimize away our sloppiness

/* replace */
x = (x - remainder)/10;
/* with */
x = x/10;

The first optimization has a great cascading effect:

• We can get rid of the for loop we had employed for constructing the return value
• With the for loop goes the Math.Pow()
• With removal of Math.Pow() goes away the need to Convert.ToInt32() and the OverflowException handling abomination
• With all of the above we also have now gotten rid of the constraint violation.

The final optimized code is

public class Solution 
{
    public int Reverse(int x)
	{
   		int returnNumber = 0;

        while(true)
        {
            returnNumber = returnNumber * 10 + x % 10;
            x = x/10;
            
            if(Math.Abs(x) < 1) break;

            if(returnNumber > Int32.MaxValue/10) return 0;
            else if(returnNumber < Int32.MinValue/10) return 0;
        }
        return returnNumber;
	}
}