LeetCode Problem

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 [-2^31, 2^31 - 1], then return 0.

Examples

Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21

Constraints

-2^31 <= x <= 2^31 - 1

Follow-up

Approach to Solve

Use a mathematical approach to reverse the digits while checking for overflow.

Code Implementation

class Solution:
    def reverse(self, x: int) -> int:
        if x < 0:
            sign = -1
            x = -x
        else:
            sign = 1
        result = 0
        while x > 0:
            result = result * 10 + x % 10
            x = x // 10
        return sign * result if result <= 2**31 - 1 else 0

class Solution {
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
            result = result * 10 + digit;
            x = x / 10;
        }
        return result;
    }
}

class Solution {
public:
    int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) return 0;
            if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) return 0;
            result = result * 10 + digit;
            x = x / 10;
        }
        return result;
    }
};

Explanation

This solution uses a mathematical approach to reverse the digits of the integer. Here's a detailed explanation of the algorithm:

Handle the sign (Python implementation):
- If the input is negative, we store the sign and work with the absolute value.
- This simplifies the reversal process.
Iterate through the digits:
- We use a while loop that continues as long as x is not zero.
- In each iteration, we extract the last digit of x using the modulo operator (%).
Build the reversed number:
- We multiply the current result by 10 to shift its digits left.
- We then add the extracted digit to the result.
- This process effectively reverses the order of the digits.
Handle overflow:
- In the Java and C++ implementations, we check for potential overflow before each operation.
- If result > INT_MAX / 10, adding another digit will definitely cause overflow.
- If result == INT_MAX / 10, we need to check if the next digit is > 7 (since 2^31 - 1 ends with 7).
- Similar checks are done for the minimum integer value.
- If overflow would occur, we return 0 as specified in the problem.
Update x:
- We divide x by 10 in each iteration to remove the last digit.
Return the result:
- In Python, we apply the sign back to the result.
- We also do a final check to ensure the result is within the 32-bit integer range.

Time Complexity: O(log(x)) because the number of digits in a number is proportional to the logarithm of the number. Space Complexity: O(1) as we only use a constant amount of extra space.

This approach is efficient and handles all edge cases, including overflow scenarios, without using any built-in functions to convert the integer to a string.

Complexity

Time Complexity: O(log(x))
Space Complexity: O(1)

LeetSolved

Reverse Integer