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 [-2^31, 2^31 - 1]
, then return 0
. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
For example:
Write a function to implement this. Discuss the time and space complexity. How would you handle edge cases such as:
The most straightforward approach is to convert the integer to a string, reverse the string, and then convert it back to an integer. We also need to handle the negative sign and check for overflow.
def reverse_integer_naive(x: int) -> int:
s = str(x)
sign = -1 if s[0] == '-' else 1
if sign == -1:
s = s[1:]
reversed_s = s[::-1]
result = sign * int(reversed_s)
# Check for 32-bit integer overflow
if result < -2**31 or result > 2**31 - 1:
return 0
return result
A more efficient solution avoids string conversions by using mathematical operations. We can extract digits one by one using the modulo operator and build the reversed integer.
def reverse_integer_optimal(x: int) -> int:
reversed_x = 0
sign = 1 if x >= 0 else -1
x = abs(x)
while x > 0:
digit = x % 10
x //= 10
# Check for potential overflow before updating reversed_x
if reversed_x > 2**31 // 10 or (reversed_x == 2**31 // 10 and digit > 7):
return 0
if reversed_x < (-2)**31 // 10 or (reversed_x == (-2)**31 // 10 and digit < -8):
return 0
reversed_x = reversed_x * 10 + digit
return sign * reversed_x
reversed_x
in each iteration of the loop.