Reverse Integer

Difficulty: Medium | Acceptance: 30.67% | Paid: No

Topics: Math

• Examples
• Constraints
• String Conversion Approach
• Mathematical Approach
• Pop and Push Digits Approach

Examples

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

String Conversion Approach

Intuition

Convert the integer to a string, reverse the string, and convert back to an integer. Handle the sign separately.

Steps

• Check if the input is negative and store the sign.
• Convert the absolute value of the integer to a string.
• Reverse the string using slicing.
• Convert the reversed string back to an integer.
• Apply the original sign to the result.
• Check if the result is within the 32-bit integer range; if not, return 0.

def reverse(x):
    INT_MIN, INT_MAX = -2**31, 2**31 - 1
    sign = -1 if x < 0 else 1
    x_str = str(abs(x))
    reversed_str = x_str[::-1]
    result = sign * int(reversed_str)
    if result < INT_MIN or result > INT_MAX:
        return 0
    return result

Complexity

• Time: O(log x) where log x is the number of digits in x
• Space: O(log x) for storing the string representation

Mathematical Approach

Intuition

Extract digits one by one from the end of the number and build the reversed number mathematically.

Steps

• Initialize a variable to store the reversed number.
• Iterate while the input number is not zero.
• In each iteration, extract the last digit using modulo 10.
• Before appending the digit to the reversed number, check for overflow.
• Append the digit to the reversed number by multiplying by 10 and adding the digit.
• Remove the last digit from the input number by integer division by 10.
• Return the reversed number after the loop.

def reverse(x):
    INT_MIN, INT_MAX = -2**31, 2**31 - 1
    sign = -1 if x < 0 else 1
    x_abs = abs(x)
    reversed_num = 0
    while x_abs != 0:
        digit = x_abs % 10
        if reversed_num > (INT_MAX - digit) // 10:
            return 0
        reversed_num = reversed_num * 10 + digit
        x_abs //= 10
    return sign * reversed_num

Complexity

• Time: O(log x) where log x is the number of digits in x
• Space: O(1) as we use only a constant amount of extra space

Pop and Push Digits Approach

Intuition

Directly manipulate the digits mathematically without converting to string, handling overflow carefully.

Steps

• Initialize the result to 0.
• Process each digit from right to left.
• For each digit, check if pushing it to the result would cause overflow.
• If overflow is detected, return 0.
• Otherwise, push the digit to the result.
• Continue until all digits are processed.
• Return the final result.

def reverse(x):
    INT_MIN, INT_MAX = -2**31, 2**31 - 1
    result = 0
    sign = -1 if x < 0 else 1
    x_abs = abs(x)
    while x_abs != 0:
        pop = x_abs % 10
        x_abs //= 10
        if result > INT_MAX // 10 or (result == INT_MAX // 10 and pop > 7):
            return 0
        if result < INT_MIN // 10 or (result == INT_MIN // 10 and pop < -8):
            return 0
        result = result * 10 + pop
    return sign * result

Complexity

• Time: O(log x) where log x is the number of digits in x
• Space: O(1) as we only use a constant amount of extra space