Reverse Integer - Leetcode #7 Short & Simple Solution
Updated: Jun 1, 2022
In our previous article we solved the two sum problem.This is another article in the series leetcode problem solutions and this article is a solution to leetcode 7 two sum problem.
Given a 32-bit signed integer x, reverse the digits in x and return the result. If after reversing, the result goes outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.
Example
Example 1
Input: x = 123
Output: 321Example 2
Input: x = -123
Output: -321Example 3
Input: x = 120
Output: 21Solution
The problem statement is pretty straightforward. We are given an integer value x, our task is to write an algorithm that reverses this given input number. Also it is stated that the given number can be negative.
If you have gone through our palindrome number article you already know that reversing an integer value was one of the sub-tasks we had to do in our palindrome number solution. The solution to this problem is almost the same as the reversing integer part described in palindrome number solution.
This problem can be efficiently solved using the divide and mod operations. The idea is to reverse the given number by applying the divide (/) and mod (%) operations on it.
To reverse the given number we need to do the following steps:
Extract last digit from right to left from the given number using the mod operator.
Put the extracted digit into its correct position in the result.
Discard the currently processed digit from the original number using divide operation.
Repeat steps 1 - 3 as long as the given value x is greater than 0.
The above steps can be represented using the formula:
result = result* 10 + currentDigit
And,
currentDigit = x%10
Lets understand this with an example:
Consider x = 369 is the given number. Lets take a variable to store our result, lets call it result. Initially result = 0.
One by one we process each digit in x from right to left, starting with the last digit 9.
Iteration 1
Step 1
Extract last digit from x using the mod operator i.e. currentDigit = x%10 = 369 % 10 = 9.
Step 2
Move currentDigit to its correct base position in result. This step is similar to the leetcode 8 problem where we had to move converted digit to its correct base position. As in leetcode 8 problem we can accomplish this by multiplying result with 10 and then adding the currentDigit to it. So result = result * 10 + currentDigit = 0 * 10 + 9 = 9.
Step 3
Now that we have processed the digit 9 completely we need to remove it from x. We can do this using the divide operation, x = x/10 = 369/10 = 36.
Iteration 2
Repeat the above three steps again for digit 6 in x = 36.
Step 1
currentDigit = x%10 = 36 % 10 = 6
Step 2
result = result * 10 + currentDigit = 9 * 10 + 6 = 96
Step 3
x = x/10 = 36/10 = 3.
Iteration 3
Again we repeat these steps for the final digit in x = 3.
Step 1
currentDigit = x%10 = 3 % 10 = 3
Step 2
result = result * 10 + currentDigit = 96 * 10 + 3 = 963
Step 3
x = x/10 = 3/10 = 0
As you can see we have successfully reversed the given number 369. Finally we return result = 963.
We do all these operations in a loop. Once x = 0 we stop our loop.
How do we handle negative number in input?
We take an integer variable signMultiplier to handle negative numbers. signMultiplier = -1 if the input number is negative and signMultiplier = 1 for positive numbers. Whenever we get a negative number we first convert it into a positive number first by multiplying it with the signMultiplier and then do the steps needed to reverse the number. Once the number is reversed we convert it back to negative number by multiplying the result again with signMultiplier.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Implementation
Language: Go
Language: Python
Language: Java
Complexity Analysis
Time Complexity: O(n)
n here is the no. of digits in the given input number. Time complexity is O(n) because we have to process each digit in the given number at least once to reverse the given number.
Space Complexity: O(1)
No extra space is used.
Reversed an integer? Its time to reverse a list now! Check it out: Reversing a list
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Code Recipe New Year Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.
https://leetcode.com/problems/reverse-integer/ Maybe description was updated at some point: «Assume the environment does not allow you to store 64-bit integers (signed or unsigned).» And 2**31 is out of bounds of the int32.
So there is a violation of the task's restrictions: min_int_32 = 2 ** 31