Jobs

Interviews

Discussions

Reverse Integer

Medium

Apple

3 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

3 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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if the reversed integer overflows, underflows, or is otherwise outside the 32-bit signed integer range?
Can the input integer be negative, positive, or zero?
Does the sign of the original integer need to be preserved in the reversed integer?
Could you provide a couple of example inputs and their corresponding expected outputs, especially for edge cases like very large positive/negative numbers or numbers ending in zero?
Is it acceptable to use built-in functions like `str()` or `Math.abs()` or should I implement the reversal and sign handling without them?

Brute Force Solution

Approach

The brute force strategy aims to find the reversed version of a number by meticulously examining each digit. It involves converting the number into a sequence of characters, reversing this sequence, and then converting it back to a number. Finally, it also includes a check to make sure that the reversed number remains within the allowed range.

Here's how the algorithm would work step-by-step:

First, determine if the given number is positive or negative and remember this fact.
If the number is negative, treat it as positive for the reversing process.
Convert the number into a sequence of digits.
Reverse the order of these digits.
Reconstruct the number from the reversed sequence of digits.
If the original number was negative, make the reversed number negative as well.
Check if the reversed number is within the maximum and minimum allowed values for integers. If it's outside this range, return zero; otherwise, return the reversed number.

Code Implementation

def reverse_integer(number):
    is_negative = number < 0

    # If negative, store the information and work with the absolute value
    if is_negative:
        number = -number

    number_string = str(number)
    reversed_string = number_string[::-1]

    try:
        reversed_number = int(reversed_string)
    except ValueError:
        return 0

    # Apply the sign that was previously removed
    if is_negative:
        reversed_number = -reversed_number

    # Check for overflow before returning the result
    if reversed_number < -2**31 or reversed_number > 2**31 - 1:
        return 0

    return reversed_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm converts the integer to a string, reverses the string, and converts it back to an integer. The conversion to and from a string takes time proportional to the number of digits in the integer, which is 'n'. Reversing the string also takes O(n) time as it iterates through each character once. Therefore, the overall time complexity is dominated by these linear operations, resulting in O(n).

Space Complexity

O(N) – The space complexity is determined by the conversion of the integer into a sequence of digits, implying a temporary storage, likely a string or a list, of size N, where N is the number of digits in the input integer. Reversing this sequence is done in place or creates another sequence of size N. Therefore, the auxiliary space is proportional to the number of digits in the input. This gives us O(N) space complexity.

Optimal Solution

Approach

To reverse an integer efficiently, we don't treat it as a normal number, but rather work on its digits one by one. The main trick is to extract the digits from the right and build the reversed number while carefully checking for potential overflow issues during the construction process.

Here's how the algorithm would work step-by-step:

Take the last digit of the original number by using modulo 10 (finding the remainder after division by 10).
Add this last digit to the reversed number, but first multiply the reversed number by 10 to make space for the new digit at the end.
Before adding the digit, check if adding the digit will cause the reversed number to become too large (overflow). If it will, we know it is outside of the valid range and should return 0 immediately.
Remove the last digit from the original number by integer division by 10.
Repeat these steps until the original number is zero.
Return the reversed number.

Code Implementation

def reverse_integer(number):
    reversed_number = 0
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31

    while number != 0:
        # Extract the last digit from the original number
        digit = number % 10
        number = int(number / 10)

        # Check for overflow before multiplying
        if reversed_number > INT_MAX // 10 or (reversed_number == INT_MAX // 10 and digit > 7):
            return 0

        # Check for underflow before multiplying
        if reversed_number < INT_MIN // 10 or (reversed_number == INT_MIN // 10 and digit < -8):
            return 0

        # Build the reversed number
        reversed_number = reversed_number * 10 + digit

    return reversed_number

Big(O) Analysis

Time Complexity

O(log(n)) – The algorithm iterates through the digits of the input integer. The number of digits in an integer 'n' is proportional to log base 10 of 'n'. The while loop continues as long as the original number is not zero, and in each iteration, it removes the last digit by dividing by 10. Thus, the number of iterations is proportional to the number of digits. Therefore, the time complexity is O(log(n)).

Space Complexity

O(1) – The algorithm uses a single variable to store the reversed integer. It also uses the input integer itself, but modifying the input in place does not contribute to auxiliary space. Therefore, the amount of extra memory used does not depend on the size of the integer N (number of digits). Thus, the space complexity is constant.

Edge Cases

Case	How to Handle
Positive integer with trailing zeros like 1200	The reversed integer will naturally drop trailing zeros; the code should not add them back.
Negative integer like -123	Store the sign, reverse the absolute value, and then apply the sign back.
Integer.MAX_VALUE (2147483647)	Reversing it will likely cause an overflow and should return 0.
Integer.MIN_VALUE (-2147483648)	Reversing it will likely cause an overflow and should return 0.
Reversed integer is slightly larger than Integer.MAX_VALUE (e.g., 2147483649)	Check for overflow before returning the reversed integer; if overflow occurs, return 0.
Reversed integer is slightly smaller than Integer.MIN_VALUE (e.g., -2147483649)	Check for underflow before returning the reversed integer; if underflow occurs, return 0.
Single-digit integer like 5	Reversing it returns the same number, which is a valid case.
Input is zero (0)	Reversing zero results in zero, which is a valid case and should be handled correctly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if the reversed integer overflows, underflows, or is otherwise outside the 32-bit signed integer range?
Can the input integer be negative, positive, or zero?
Does the sign of the original integer need to be preserved in the reversed integer?
Could you provide a couple of example inputs and their corresponding expected outputs, especially for edge cases like very large positive/negative numbers or numbers ending in zero?
Is it acceptable to use built-in functions like `str()` or `Math.abs()` or should I implement the reversal and sign handling without them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine if the given number is positive or negative and remember this fact.
If the number is negative, treat it as positive for the reversing process.
Convert the number into a sequence of digits.
Reverse the order of these digits.
Reconstruct the number from the reversed sequence of digits.
If the original number was negative, make the reversed number negative as well.
Check if the reversed number is within the maximum and minimum allowed values for integers. If it's outside this range, return zero; otherwise, return the reversed number.

Code Implementation

def reverse_integer(number):
    is_negative = number < 0

    # If negative, store the information and work with the absolute value
    if is_negative:
        number = -number

    number_string = str(number)
    reversed_string = number_string[::-1]

    try:
        reversed_number = int(reversed_string)
    except ValueError:
        return 0

    # Apply the sign that was previously removed
    if is_negative:
        reversed_number = -reversed_number

    # Check for overflow before returning the result
    if reversed_number < -2**31 or reversed_number > 2**31 - 1:
        return 0

    return reversed_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the last digit of the original number by using modulo 10 (finding the remainder after division by 10).
Add this last digit to the reversed number, but first multiply the reversed number by 10 to make space for the new digit at the end.
Before adding the digit, check if adding the digit will cause the reversed number to become too large (overflow). If it will, we know it is outside of the valid range and should return 0 immediately.
Remove the last digit from the original number by integer division by 10.
Repeat these steps until the original number is zero.
Return the reversed number.

Code Implementation

def reverse_integer(number):
    reversed_number = 0
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31

    while number != 0:
        # Extract the last digit from the original number
        digit = number % 10
        number = int(number / 10)

        # Check for overflow before multiplying
        if reversed_number > INT_MAX // 10 or (reversed_number == INT_MAX // 10 and digit > 7):
            return 0

        # Check for underflow before multiplying
        if reversed_number < INT_MIN // 10 or (reversed_number == INT_MIN // 10 and digit < -8):
            return 0

        # Build the reversed number
        reversed_number = reversed_number * 10 + digit

    return reversed_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Positive integer with trailing zeros like 1200	The reversed integer will naturally drop trailing zeros; the code should not add them back.
Negative integer like -123	Store the sign, reverse the absolute value, and then apply the sign back.
Integer.MAX_VALUE (2147483647)	Reversing it will likely cause an overflow and should return 0.
Integer.MIN_VALUE (-2147483648)	Reversing it will likely cause an overflow and should return 0.
Reversed integer is slightly larger than Integer.MAX_VALUE (e.g., 2147483649)	Check for overflow before returning the reversed integer; if overflow occurs, return 0.
Reversed integer is slightly smaller than Integer.MIN_VALUE (e.g., -2147483649)	Check for underflow before returning the reversed integer; if underflow occurs, return 0.
Single-digit integer like 5	Reversing it returns the same number, which is a valid case.
Input is zero (0)	Reversing zero results in zero, which is a valid case and should be handled correctly.