Reverse Integer
Problem Description
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
Constraints:
- -231 <= x <= 231 - 1
Solve it on LeetCode
Approaches
1. String Manipulation
This simple approach involves converting the integer to a string, reversing it and converting it back to an integer. While naive, it's straightforward to implement and understand.
Code:
- Time Complexity: O(n), where n is the number of digits in the integer. This results from reversing the string representation of the integer.
- Space Complexity: O(1) ignoring the space used for input and output as this uses a constant amount of space for the StringBuilder operations.
2. Mathematical Reverse
Instead of using built-in string manipulation, this approach repeatedly divides the input by 10 to extract digits and form the reversed integer.
Code:
- Time Complexity: O(log(x)), where x is the input integer. We extract each digit one by one and combine it in reversed order.
- Space Complexity: O(1), since we're using a fixed amount of extra space.
3. Optimized Mathematical Reverse with Overflow Check
Handling overflow is crucial because the problem constraints specify that the reversed integer must fit within a 32-bit signed integer range. This can be efficiently achieved by checking possible overflow conditions before updating the result in each iteration.
Code:
- Time Complexity: O(log(x)), similar to the previous mathematical approach, handling each digit once.
- Space Complexity: O(1), as we use a minimal, constant amount of additional space for variables.