Reverse Integer

Problem Statement: Given a 32-bit signed integer, reverse its digits.

1. Clarify the problem:

• Can we assume that the input is always a 32-bit signed integer?
• How do we handle overflow if the reversed integer exceeds the 32-bit signed integer range?

2. Analyze the problem:

• Input: 32-bit signed integer
• Output: Reversed integer
• Constraints:
  • The reversed integer should be within the range of a 32-bit signed integer.

3. Design an algorithm:

• Convert the input integer to a string for easier manipulation.
• Handle the sign separately.
• Reverse the string.
• Convert the reversed string back to an integer and handle overflow if necessary.

4. Explain your approach:

• We will convert the input integer to a string to make it easier to manipulate the digits.
• We will handle the sign separately by checking if the input is negative and storing the sign for later use.
• We will reverse the string using string slicing or a loop.
• Finally, we will convert the reversed string back to an integer and handle overflow by checking if the result exceeds the 32-bit signed integer range.

5. Write clean and readable code:

python

class Solution:
    def reverse(self, x):
        sign = -1 if x < 0 else 1
        x_str = str(abs(x))
        reversed_str = x_str[::-1]
        reversed_int = int(reversed_str) * sign

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

        return reversed_int

6. Test your code: Let's test the code with some example and additional test cases:

python

# Example test cases
solution = Solution()
x = 123
print(solution.reverse(x))
# Expected output: 321

x = -123
print(solution.reverse(x))
# Expected output: -321

x = 120
print(solution.reverse(x))
# Expected output: 21

# Additional test cases
x = 0
print(solution.reverse(x))
# Expected output: 0

x = 1
print(solution.reverse(x))
# Expected output: 1

x = 1534236469
print(solution.reverse(x))
# Expected output: 0 (overflow)

x = -2147483648
print(solution.reverse(x))
# Expected output: 0 (overflow)

7. Optimize if necessary: The provided solution has a time complexity of O(log10(x)) as we convert the input integer to a string and reverse it. The space complexity is O(log10(x)) as well since we store the reversed string.

8. Handle error cases: The code handles the case where the reversed integer exceeds the range of a 32-bit signed integer. If the reversed integer is outside the valid range, the code returns 0.

9. Discuss complexity analysis: The time complexity of the solution is O(log10(x)), where x is the absolute value of the input integer. This is because we convert the input integer to a string and reverse it, which takes logarithmic time with respect to the value of the integer. The space complexity is also O(log10(x)) as we store the reversed string. The solution is optimal in terms of time complexity, but the space complexity could be improved by using mathematical operations instead of string manipulation. However, this would make the code less readable and more error-prone.