Reverse Integer
Medium
2 views
Topics:
Bit Manipulation
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the expected behavior if the reversed integer overflows the 32-bit signed integer range? Should I return 0, or is there another specified return value?
- Can the input integer be negative? If so, how should the sign be handled during the reversal?
- Is the input guaranteed to be an integer, or do I need to handle potential non-integer input?
- Are there any leading zeros I need to consider in the input (although this is less likely for integer inputs)?
- Could the input be zero? If so, what is the expected output in that specific case?
Brute Force Solution
Approach
The brute force way to reverse an integer is like doing it manually. We'll look at the number digit by digit and build a new reversed number. We need to also handle any negative signs.
Here's how the algorithm would work step-by-step:
- First, figure out if the number is positive or negative and remember that information.
- Next, take the absolute value of the number, so we only deal with positive numbers.
- Now, look at the last digit of the number. Make that the first digit of our new, reversed number.
- Then, chop off the last digit of the original number.
- Repeat the process of taking the last digit and adding it to the beginning of our reversed number, and then chopping off the last digit of the original number, until the original number is zero.
- If the original number was negative, put the negative sign back on the front of the reversed number.
- Finally, check if the reversed number is still within the allowed range for integers. If it's too big or too small, we can't use it.
Code Implementation
def reverse_integer(integer_to_reverse):
is_negative = integer_to_reverse < 0
# Convert to positive to simplify the reversing process
if is_negative:
integer_to_reverse = -integer_to_reverse
reversed_integer = 0
while integer_to_reverse > 0:
# Extract the last digit
last_digit = integer_to_reverse % 10
# Build the reversed integer
reversed_integer = (reversed_integer * 10) + last_digit
# Remove the last digit from original integer
integer_to_reverse //= 10
# Restore the negative sign if the original was negative
if is_negative:
reversed_integer = -reversed_integer
# Check for 32-bit integer overflow
if reversed_integer < -2**31 or reversed_integer > 2**31 - 1:
return 0
return reversed_integerBig(O) Analysis
Time Complexity
O(log(x)) – The primary operation is extracting digits from the integer x until it becomes zero. The number of iterations in the while loop is determined by the number of digits in x. The number of digits in an integer x is proportional to log(x). Thus, the time complexity is O(log(x)), where x is the input integer. This is because each division by 10 effectively reduces the problem size logarithmically.
Space Complexity
O(1) – The algorithm uses a few variables to store the sign of the number and the reversed integer. The number of variables remains constant regardless of the size of the input integer. Therefore, the algorithm uses constant extra space.
Optimal Solution
Approach
The best way to reverse an integer is to build the reversed number one digit at a time. We carefully extract digits from the original number and add them to the reversed number, while watching out for potential overflow issues before they happen.
Here's how the algorithm would work step-by-step:
- Take the original number and repeatedly get its last digit.
- Build the reversed number by adding the last digit of the original number to the end of the reversed number.
- Before adding a digit, check if adding this digit would cause the reversed number to become too big or too small (overflow). If it would, stop and return an error (0).
- Remove the last digit from the original number.
- Repeat until the original number is zero.
Code Implementation
def reverse_integer(number):
reversed_number = 0
is_negative = number < 0
if is_negative:
number = -number
while number > 0:
# Extract the last digit to append to reversed number.
last_digit = number % 10
# Check for potential overflow before adding the digit.
if reversed_number > 214748364 or \
(reversed_number == 214748364 and last_digit > 7):
return 0
if reversed_number < -214748364 or \
(reversed_number == -214748364 and last_digit < -8):
return 0
reversed_number = (reversed_number * 10) + last_digit
# Integer division to remove the last digit.
number //= 10
if is_negative:
reversed_number = -reversed_number
return reversed_numberBig(O) Analysis
Time Complexity
O(log(x)) – The runtime is determined by the number of digits in the input integer x. In each iteration of the while loop, we are effectively removing the last digit of x. The number of digits in an integer x is proportional to log(x) (base 10). Thus, the while loop iterates a number of times proportional to log(x). Therefore, the time complexity is O(log(x)).
Space Complexity
O(1) – The algorithm operates by modifying integer values and storing the reversed integer in a single variable. It uses a few constant space variables to store the current digit and the reversed number. The space used does not depend on the size of the input integer. Therefore, the auxiliary space complexity is constant.
Edge Cases
| Case | How to Handle |
|---|---|
| Positive integer with leading zeros | The reversal process will naturally remove the leading zeros. |
| Negative integer with leading zeros | The sign should be preserved and the reversal will handle removing leading zeros. |
| Integer is zero | Reversing zero should return zero. |
| Maximum positive 32-bit integer (2147483647) | The reversal must check for overflow before returning the result. |
| Minimum negative 32-bit integer (-2147483648) | The reversal must check for underflow (becoming smaller than the minimum) before returning the result. |
| Reversed integer overflows positive range | Return 0 if the reversed integer is greater than 2147483647. |
| Reversed integer overflows negative range | Return 0 if the reversed integer is less than -2147483648. |
| Integer ends with zero after reversing | The solution does not need to handle trailing zeros because they'll be naturally added after a full reversal. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
