Reverse Integer

Medium

Apple

0 views

Topics:

Bit Manipulation

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. Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

For example:

Input: x = 123, Output: 321
Input: x = -123, Output: -321
Input: x = 120, Output: 21

Write a function to implement this. Discuss the time and space complexity. How would you handle edge cases such as:

Positive and negative numbers
Trailing zeros
Integer overflow

Reverse Integer

Medium

Apple

0 views

Topics:

Bit Manipulation

For example:

Input: x = 123, Output: 321
Input: x = -123, Output: -321
Input: x = 120, Output: 21

Write a function to implement this. Discuss the time and space complexity. How would you handle edge cases such as:

Positive and negative numbers
Trailing zeros
Integer overflow

Solution

Naive Solution

The most straightforward approach is to convert the integer to a string, reverse the string, and then convert it back to an integer. We also need to handle the negative sign and check for overflow.

def reverse_integer_naive(x: int) -> int:
    s = str(x)
    sign = -1 if s[0] == '-' else 1
    if sign == -1:
        s = s[1:]
    reversed_s = s[::-1]
    result = sign * int(reversed_s)
    
    # Check for 32-bit integer overflow
    if result < -2**31 or result > 2**31 - 1:
        return 0
    return result

Time Complexity: O(N), where N is the number of digits in the integer.
Space Complexity: O(N), due to the string conversion.

Optimal Solution

A more efficient solution avoids string conversions by using mathematical operations. We can extract digits one by one using the modulo operator and build the reversed integer.

def reverse_integer_optimal(x: int) -> int:
    reversed_x = 0
    sign = 1 if x >= 0 else -1
    x = abs(x)

    while x > 0:
        digit = x % 10
        x //= 10

        # Check for potential overflow before updating reversed_x
        if reversed_x > 2**31 // 10 or (reversed_x == 2**31 // 10 and digit > 7):
            return 0
        if reversed_x < (-2)**31 // 10 or (reversed_x == (-2)**31 // 10 and digit < -8):
            return 0

        reversed_x = reversed_x * 10 + digit

    return sign * reversed_x

Time Complexity: O(log(N)), where N is the input number. This is because the number of iterations in the while loop is proportional to the number of digits in the input, which is logarithmic in terms of the number's value.
Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

Positive and Negative Numbers: The code handles both positive and negative numbers correctly by storing the sign and working with the absolute value of the input.
Trailing Zeros: Trailing zeros are automatically handled as the modulo operation effectively skips them.
Overflow: The most crucial edge case is handling 32-bit integer overflow. The optimal solution checks for overflow before updating reversed_x in each iteration of the loop.
Zero: If the input is 0, the function returns 0 directly, which is the expected behavior.

Solution

Naive Solution

The most straightforward approach is to convert the integer to a string, reverse the string, and then convert it back to an integer. We also need to handle the negative sign and check for overflow.

def reverse_integer_naive(x: int) -> int:
    s = str(x)
    sign = -1 if s[0] == '-' else 1
    if sign == -1:
        s = s[1:]
    reversed_s = s[::-1]
    result = sign * int(reversed_s)
    
    # Check for 32-bit integer overflow
    if result < -2**31 or result > 2**31 - 1:
        return 0
    return result

Time Complexity: O(N), where N is the number of digits in the integer.
Space Complexity: O(N), due to the string conversion.

Optimal Solution

A more efficient solution avoids string conversions by using mathematical operations. We can extract digits one by one using the modulo operator and build the reversed integer.

def reverse_integer_optimal(x: int) -> int:
    reversed_x = 0
    sign = 1 if x >= 0 else -1
    x = abs(x)

    while x > 0:
        digit = x % 10
        x //= 10

        # Check for potential overflow before updating reversed_x
        if reversed_x > 2**31 // 10 or (reversed_x == 2**31 // 10 and digit > 7):
            return 0
        if reversed_x < (-2)**31 // 10 or (reversed_x == (-2)**31 // 10 and digit < -8):
            return 0

        reversed_x = reversed_x * 10 + digit

    return sign * reversed_x

Time Complexity: O(log(N)), where N is the input number. This is because the number of iterations in the while loop is proportional to the number of digits in the input, which is logarithmic in terms of the number's value.
Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

Positive and Negative Numbers: The code handles both positive and negative numbers correctly by storing the sign and working with the absolute value of the input.
Trailing Zeros: Trailing zeros are automatically handled as the modulo operation effectively skips them.
Overflow: The most crucial edge case is handling 32-bit integer overflow. The optimal solution checks for overflow before updating reversed_x in each iteration of the loop.
Zero: If the input is 0, the function returns 0 directly, which is the expected behavior.