LeetCode 7 - Reverse Integer

Question:

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³¹, 2³¹ - 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

Answer:

The problem requires reversing the digits of an integer while checking for overflow conditions. The intuition behind the solution is to iteratively extract the last digit of the given number, check for potential overflow before updating the reversed result, and then continue the process until the original number becomes zero.

Approach 1 :

Initialize a variable reversed to store the result.
Iterate through the digits of the original number using a while loop.
Extract the last digit using x % 10 and update x by dividing it by 10.
Check for potential overflow conditions before updating the reversed result.
If any overflow condition is met, return 0.
Update the reversed result by multiplying it by 10 and adding the extracted digit.
Repeat steps 3-6 until the original number becomes zero.
Return the final reversed result.

Time complexity :

O(log(x))

Space complexity:

O(1)

Code:

class Solution:
    def reverse(self, x: int) -> int:
        reversed_num = 0

        while x != 0:
            digit = x % 10
            # Check for overflow before updating reversed_num
            if reversed_num > (2**31 - 1) // 10 or (reversed_num == (2**31 - 1) // 10 and digit > 7):
                return 0  # Overflow will occur if we update reversed_num
            if reversed_num < -(2**31) // 10 or (reversed_num == -(2**31) // 10 and digit < -8):
                return 0  # Overflow will occur if we update reversed_num

            reversed_num = reversed_num * 10 + digit
            x //= 10

        return reversed_num

Approach 2:

The approach is to iteratively extract the last digit of the given number, multiply the current result by 10, and add the extracted digit. The process continues until the original number becomes zero. To handle overflow, a long variable (ans) is used to store the result. After the loop, the final result is checked against the limits of a 32-bit signed integer (Integer.MAX_VALUE and Integer.MIN_VALUE). If the result is within the valid range, it is cast to an int and returned; otherwise, 0 is returned.

Time complexity:

O(log(x))

Space complexity:

O(1)

Code:

class Solution:
    def reverse(self, x: int) -> int:
        ans = 0
        while x != 0:
            ans = ans * 10 + x % 10
            x //= 10

        if ans > 2**31 - 1 or ans < -(2**31):
            return 0

        return ans