Problem 7 - Reverse Integer (Easy)
Code for this problem can be found at https://github.com/scprogramming/LeetcodeExplained/tree/master/Problem%20Seven%20-%20Reverse%20Integer%20(Easy)
Problem: Given a positive or negative integer, reverse the digits of the integer and return the results.
This problem on the surface looks easy, and there are a few different ways to solve it. First, I will present a method that makes use of stacks to solve the problem. After this, we will examine a way of reversing the digits using only some math and a few basic checks.
Method 1: The String Stack Method
Using a stack, we can easily design an algorithm that will solve this problem. First, let's look at two example instances of the problem.
Suppose we are given the input as 123. This would mean the result is 321, the digits are just reversed. The negative number case is a little more interesting. If we are given -123, we should output -321. The negative sign needs to stay at the front regardless.
Knowing this, we can now implement our solution. We start by creating an empty stack, and iterating the integer provided as a string. Every character we encounter that isn't a "-" is placed on the stack. Since a stack stores data in a last in, first out ordering, the result in the stack will be the reversed integer. All we would need to do is pop off the values and we are done.
If we encounter a "-", we can simply set a flag to say that the provided number is negative. We can then just check the flag, and if it is true, we add the negative sign to the output. We could also just check the first character at the beginning of the function, which is what I opt to do in my code. The following code is the full implementation of the solution:
You can see that this code is short and pretty good in terms of time complexity. The first if statement checks if we have a negative number, and if so, it adds the negative sign to the output, and removes the negative sign from the string version of the input. From here, we iterate once to add the characters to the stack, then iterate again to remove them off the stack. In total, we need to iterate n times for the first stack push, then n times for the stack pop. This gives us a total time complexity of O(n).
The issue with this implementation is that some programming languages won't come with a stack implementation, and sometimes memory is also a constraint we want to consider. If we are short on memory, or unable to use a stack, the next solution could work well for us instead.
Method 2: Using Math to Parse Integers
Let's revisit our examples again. Suppose that the number inputted is 123, and we want to parse it without a stack. We want to be able to extract the last digit from this number. To do this, we can use the modulus operation, to calculate the mod of the value against 10. This will give us the digit in the last position. So, for this example, we would have:
123 % 10 = 3
Once we do this, we simply need to do an integer division of the original number to remove the last digit and continue. So, we have:
123 / 10 = 12
12 % 10 = 2
12 / 10 = 1
1 % 19 = 1
As you can see, this worked for our example. Now that we know how to extract the single digits, we just need to get them appended to the returned integer. To do this, we can use a simple formula. Let rev be the variable storing the reversed integer, and let pop be the digit we just removed.
Temp = rev * 10 + pop
Rev = temp
Let's see this in action from our example. Here is our first iteration:
Rev = 0
Input = 123
Pop = input % 10 = 3
Input = input / 10 = 12
Temp = rev * 10 + pop = 0 * 10 + 3 = 3
Our second iteration:
Rev = 3
Input = 12
Pop = input % 10 = 2
Input = input / 10 = 1
Temp = rev * 10 + pop = 3 * 10 + 2 = 32
You can see how this would eventually result in the correct reversed string. There is however one more consideration we should make before we are complete. If the number of negative, our current algorithm doesn't really work. Similar to before, we just need to check for a negative before proceeding and remove it until the end. The full code is as follows:
You can see that I first check if the integer provided is < 0, and if it is, I take the absolute value, and set the negative number flag to true. From here I proceed as discussed, taking the modulus and division, and placing it on rev. Finally, if the negative flag is set, I subtract rev by itself times 2. This will give me the negative of the result.
All in all, this algorithm is slightly better than the first algorithm. Given that it iterates for each digit, reducing the size by 10 on each iteration, the time complexity is O(log(n)), where n is the number of digits in the input.
One further enhancement you may need to consider is what happens if the reverse value is bigger than the maximum integer size. This can be done by just checking if the result will overflow, and acting accordingly (typically by setting the value to zero).