7. Reverse Integer
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 25.9%
Problem Breakdown
The problem requires reversing the digits of a given signed 32-bit integer x. The output should be the reversed integer. If the reversed integer exceeds the 32-bit signed integer range [-2^31, 2^31 - 1], we return 0. The environment does not allow storing 64-bit integers.
Inputs:
- A signed 32-bit integer
x.
Outputs:
- The reversed integer of
xor 0 if it overflows the 32-bit range.
Implicit Constraints/Tricky Edge Cases:
- Negative numbers.
- Numbers ending with zero (e.g., 120 should reverse to 21).
- Zero itself, which remains unchanged.
- Overflow conditions where the reversed number exceeds the 32-bit signed integer range.
Intuition
A brute-force approach would involve converting the integer to a string, reversing the string, and then converting it back to an integer. However, this approach is inefficient in terms of space complexity because it uses additional storage for the string representation.
The key insight is to reverse the digits mathematically by repeatedly extracting the last digit of the number and building the reversed number step by step. This avoids the need for extra space and directly handles the overflow condition by checking if the current result will exceed the 32-bit range before multiplying it by 10.
Approach
- Initialize a variable
reversed_numto 0. - Use a loop to process each digit of the input integer
x:- Extract the last digit using
x % 10. - Check if adding this digit to
reversed_numwould cause an overflow or underflow by comparing it against the limits of a 32-bit signed integer. - If it would, return 0.
- Otherwise, update
reversed_numby multiplying it by 10 and adding the extracted digit. - Remove the last digit from
xusing integer divisionx //= 10.
- Extract the last digit using
- Return the
reversed_num.
Complexity Analysis
- Time Complexity: O(log10|x|), where |x| is the absolute value of
x. This is because we process each digit of the number. - Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def reverse(x: int) -> int:
INT_MAX = 2**31 - 1
INT_MIN = -2**31
reversed_num = 0
while x != 0:
digit = x % 10
# Check for overflow and underflow before actually reversing the digits
if reversed_num > (INT_MAX // 10) or (reversed_num == (INT_MAX // 10) and digit > 7):
return 0
if reversed_num < (INT_MIN // 10) or (reversed_num == (INT_MIN // 10) and digit < -8):
return 0
reversed_num = reversed_num * 10 + digit
x //= 10
return reversed_num
Edge Cases Handled
- Negative numbers: The code correctly handles negative numbers by checking the sign during overflow/underflow conditions.
- Numbers ending with zero: The last digit is removed in each iteration, so trailing zeros are not included in the reversed number.
- Zero itself: The loop does not execute for
x = 0, and the function returns 0 immediately. - Overflow/Underflow: The code checks if adding a new digit would cause an overflow or underflow before updating
reversed_num. If it would, the function returns 0.