Reverse Integer
Problem Statement
You are given a signed 32-bit integer x
.
Return x
after reversing its digits. After reversing, if x
goes outside the signed 32-bit integer range [-2^31, 2^31 - 1]
, then return 0
instead.
Solve the problem without using integers that are outside the signed 32-bit integer range.
Example 1:
Input: x = 1234
Output: 4321
Example 2:
Input: x = -1234
Output: -4321
Example 3:
Input: x = 1234236467
Output: 0
Constraints:
-2^31 <= x <= 2^31 - 1
Recommended Time and Space Complexity
The time complexity should be O(log(x))
and the space complexity should be O(1)
.
Hint 1
How would you extract the last digit of a number?
Hint 2
How can you build the reversed number digit by digit?
Hint 3
Consider the overflow conditions.
Solution
Brute Force
def reverse(x: int) -> int: original = x x = abs(x) reversed_x = int(str(x)[::-1]) if original < 0: reversed_x *= -1 if reversed_x < -(1 << 31) or reversed_x > (1 << 31) - 1: return 0 return reversed_x
Time complexity: O(log(x))
Space complexity: O(1)
Recursion
def reverse(x: int) -> int: def rec(n: int, rev: int) -> int: if n == 0: return rev
rev = rev * 10 + n % 10 return rec(n // 10, rev)
sign = -1 if x < 0 else 1 x = abs(x) reversed_num = rec(x, 0) reversed_num *= sign if reversed_num < -(1 << 31) or reversed_num > (1 << 31) - 1: return 0
return reversed_num
Time complexity: O(log(x))
Space complexity: O(log(x))
Iteration
import math
def reverse(x: int) -> int: minimum = -2147483648 # -2^31, maximum = 2147483647 # 2^31 - 1
result = 0 while x: digit = int(math.fmod(x, 10)) x = int(x / 10)
if result > maximum // 10 or (result == maximum // 10 and digit > maximum % 10): return 0 if result < minimum // 10 or (result == minimum // 10 and digit < minimum % 10): return 0 result = (result * 10) + digit
return result
Time complexity: O(log(x))
Space complexity: O(1)