algoadvance

Given a 32-bit signed 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.

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

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

Clarifying Questions

1. Should we handle edge cases where the input might be 0?
   • Yes, 0 is a valid input and the output should be 0.
2. Talking about the output limitations, should we return 0 in any case where the result goes beyond the 32-bit signed integer range?
   • Yes, if the reversed integer is out of bounds, we should return 0.

Strategy

1. Extract the Sign and Convert to String:
   • Extract the sign of the integer to handle it separately.
   • Convert the absolute value of the integer to a string.
2. Reverse the String:
   • Reverse the string representation of the integer.
3. Convert Back to Integer and Restore the Sign:
   • Convert the reversed string back to an integer and reapply the original sign.
4. Check for 32-bit Overflow:
   • Ensure that the reversed integer is within the 32-bit signed integer range.
5. Edge Cases:
   • Handle the edge case where the result goes beyond the 32-bit signed integer range by returning 0.

Code

Let’s implement the proposed solution:

def reverse(x: int) -> int:
    # Check the sign of the integer
    sign = -1 if x < 0 else 1
    
    # Convert to string, strip the sign, reverse the string, and convert back to integer
    reversed_int = int(str(abs(x))[::-1])
    
    # Apply the original sign
    reversed_int *= sign
    
    # Check for 32-bit signed integer overflow
    if reversed_int < -2**31 or reversed_int > 2**31 - 1:
        return 0
    
    return reversed_int

# Test cases
print(reverse(123))    # Expected output: 321
print(reverse(-123))   # Expected output: -321
print(reverse(120))    # Expected output: 21
print(reverse(0))      # Expected output: 0
print(reverse(1534236469))  # Expected output: 0 (since reversed value overflows)

Time Complexity

• Conversion to String: (O(n)), where (n) is the number of digits in x.
• Reversing the String: (O(n)), linear time for reversing the string.
• Conversion back to Integer: (O(n)), linear time for conversion.
• Overall Time Complexity: (O(n)) since all steps are linear in the number of digits.

Space Complexity

• Storage for String Representation: (O(n)), where (n) is the number of digits in x.
• Overall Space Complexity: (O(n)) due to the storage of the string representation of the integer.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?