codingcircle » 7. Reverse Integer

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³¹, 2³¹ - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Constraints:

-2³¹ <= x <= 2³¹ - 1

Problem Description

The task is to take a signed 32-bit integer x and reverse the order of its digits. For example, if the input is 123, the output should be 321. If the input is -123, the output should be -321. The tricky part comes with the boundaries of a 32-bit signed integer, which ranges from -2^31 to 2^31 - 1. If reversing the digits of x would cause the number to fall outside this range, the function should return 0 instead. This means we need to be careful with overflow—an issue that occurs when the reversed integer is too large or too small to be represented by a 32-bit signed integer.

Intuition

To solve this problem, we first set up two boundaries, mi and mx, which represent the minimum and maximum values of a 32-bit signed integer, respectively. These values are -2^31 and 2^31 - 1.

We want to build the reversed number digit by digit. We can isolate the last digit of x by taking x % 10 (the remainder when x is divided by 10). This last digit, referred to as y in our code, is the next digit to be placed in the reversed number.

However, we need to be careful not to cause an overflow when we add this new digit to the reversed number. Before we add y to the reversed number ans, we check if adding the digit would cause an overflow. To do this, we check if ans is either less than mi / 10 + 1 or greater than mx / 10. If it’s outside this range, we return 0.

If it’s safe to add the digit, we proceed. We add the digit to ans by multiplying ans by 10 (which “shifts” the current digits to the left) and then adding y. This process effectively reverses the digits of x.

For the next iteration, we need to remove the last digit from x. We do this by subtracting y from x and then dividing by 10.

We repeat this process until x has no more digits left. The result is a reversed number that fits within the 32-bit signed integer range, or 0 if an overflow would have occurred.

The time complexity is O(\log |x|) because the process continues for as many digits as x has, and the space complexity is O(1) as there is a constant amount of memory being used regardless of the size of x.

Solution Approach

The implementation uses a straightforward algorithm that iterates through the digits of the input number x and constructs the reversed number without using additional data structures or complex patterns. Let’s detail the steps using the provided Reference Solution Approach:

Initialization: We start by setting the initial reversed number ans to 0. We also define the minimum and maximum values mi and mx for a 32-bit signed integer, which are -2^31 and 2^31 - 1.
Reversing Digits: The while loop runs as long as there are digits left in x. Within the loop, we take the following steps:
- Isolate the last digit y of x by computing x % 10.
- If x is negative and y is positive, adjust y by subtracting 10 to make it negative.
Checking for Overflow: Before appending y to ans, we must confirm that ans * 10 + y will not exceed the boundaries set by mi and mx. To avoid overflow, we check:
- If ans is less than mi/10 + 1 or greater than mx/10, we return 0 immediately, as adding another digit would exceed the 32-bit signed integer limits.
Building the Reversed Number: If it is safe to proceed, we multiply ans by 10 (which shifts the reversed number one place to the left) and add y to ans. This action reverses y from its position in x to its new reversed position in ans.
Updating the Original Number x: We update x by removing its last digit. This is done by subtracting y from x and then dividing by 10.
Completion: The loop repeats this process, accumulating the reversed number in ans until all digits are processed.

The core of this approach is predicated on the mathematical guarantees regarding integer division and modulus operations in Python. The guard checks for overflow by considering both scale (multiplication by 10) and addition (adding the digit) separately and only proceeds if the operation stays within bounds.

By following the constraints of a 32-bit signed integer at every step and efficiently using arithmetic operations, the reverse function achieves the reversal of digits robustly and efficiently.

Example Walkthrough

To illustrate the solution approach, let’s take x = 1469 as our example.

Initialization:
- ans is initialized to 0.
- mi is set to -2^31 (-2147483648).
- mx is set to 2^31 - 1 (2147483647).
Reversing Digits: Begin while loop with x = 1469.
- Isolate the last digit y by computing 1469 % 10 = 9.
- x is positive so we keep y = 9.
Checking for Overflow:
- ans is currently 0, which is greater than mi/10 + 1 (-214748364) and less than mx/10 (214748364), so continue without returning 0.
Building the Reversed Number:
- We multiply ans by 10, which is still 0, and add y to get ans = 9.
Updating the Original Number x:
- Update x to remove the last digit: x = (1469 - 9) / 10 which simplifies to x = 146.

Next iteration of the loop with x = 146:

Isolate y = 146 % 10 = 6.
Check for overflow: ans = 9 is still within bounds.
Update ans: ans = 9 * 10 + 6 = 96.
Update x: x = (146 - 6) / 10 which simplifies to x = 14.

Next iteration with x = 14:

Isolate y = 14 % 10 = 4.
Check for overflow: ans = 96 is still within bounds.
Update ans: ans = 96 * 10 + 4 = 964.
Update x: x = (14 - 4) / 10 which simplifies to x = 1.

Final iteration with x = 1:

Isolate y = 1 % 10 = 1.
Check for overflow: ans = 964 is still within bounds.
Update ans: ans = 964 * 10 + 1 = 9641.
Update x: x = (1 - 1) / 10 which simplifies to x = 0.

Now x = 0, the while loop terminates, and the reversed number ans = 9641 is returned. There were no issues with overflow throughout the process, so the result 9641 is the correct reversed integer for our example of x = 1469.

This process demonstrates that by evaluating the overflow conditions before each digit is added to the reversed number, and by building the reversed number step by step, it’s possible to safely reverse the digits of x without using extra space or complex data structures. Additionally, due to the use of modulo and division operations, the solution efficiently handles the reversal process for each digit.

Solution Implementation

class Solution {
public:
    int reverse(int x) {
        int ans = 0; // Initialize the reversed number to 0
        while (x != 0) {
            int digit = x % 10; // Get the last digit of x
            
            // Check for overflow/underflow before updating ans
            if ((ans > INT_MAX / 10) || (ans < INT_MIN / 10)) {
                return 0; // Return 0 if reversing x would cause overflow/underflow
            }
            
            ans = ans * 10 + digit; // Append the digit to the reversed number
            x = x / 10; // Remove the last digit from x
        }
        return ans; // Return the reversed number
    }
};

Copied!

class Solution {
    public int reverse(int x) {
        // Initialize the result to 0
        int res = 0;
        
        // Check if the input number is negative
        boolean isNegative = x < 0;
        
        // Convert the absolute value of the integer to a string and reverse it
        String strX = String.valueOf(Math.abs(x));
        StringBuilder sb = new StringBuilder(strX).reverse();
        
        try {
            // Try to parse the reversed string back into an integer
            res = Integer.parseInt(sb.toString());
        } catch (NumberFormatException e) {
            // If overflow occurs during parsing, return 0
            return 0;
        }
        
        // If the number was negative, negate the result; otherwise, return the result
        return isNegative ? -res : res;       
    }
}

Copied!

class Solution:
 def reverse(self, x: int) -> int:
     res = 0
     
     # Check if the number is negative
     if x < 0:
         # Reverse the string representation of the number (excluding the minus sign), then make it negative
         res = int(str(x)[1:][::-1]) * -1
     else:
         # Reverse the string representation of the number
         res = int(str(x)[::-1])
     
     # Check if the result is within the 32-bit integer range
     if res > 2 ** 31 - 1 or res < -2 ** 31:
         return 0  # Return 0 if it exceeds the 32-bit signed integer range
     
     return res  # Return the reversed integer

Copied!

int reverse(int x) {
    int rev = 0;  // Initialize the reversed number as 0

    // Loop through each digit of the number until x becomes 0
    while (x != 0) {
        // Check if the reversed number will overflow beyond the 32-bit integer range
        if (rev > INT_MAX / 10 || rev < INT_MIN / 10) 
            return 0;  // Return 0 if overflow is detected

        // Add the last digit of x to the reversed number and shift the digits
        rev = rev * 10 + (x % 10);
        
        // Remove the last digit from x
        x /= 10;
    }

    // Return the final reversed number
    return rev;
}

Copied!

public class Solution 
{
    public int Reverse(int x)
    {
        var result = 0;  // Initialize the result variable to 0

        // Loop until all digits of the number have been processed
        while (x != 0)
        {
            var remainder = x % 10;  // Get the last digit of x
            var temp = result * 10 + remainder;  // Calculate the potential new value for result

            // In case of overflow, the current value will not be equal to the previous one
            if ((temp - remainder) / 10 != result)
            {
                return 0;  // Return 0 if overflow is detected
            }

            result = temp;  // Update the result with the new value
            x /= 10;  // Remove the last digit from x
        }
        
        // Return the final reversed number
        return result;
    }
}

Copied!

var reverse = function(x) {
    let res = 0;  // Initialize the result variable to 0
    
    // If x is negative, reverse the digits and multiply by -1
    if (x < 0) {
        res = parseInt(String(x).slice(1).split('').reverse().join('')) * -1;  // Remove the negative sign, reverse digits, and add the negative sign
    } else {
        // If x is positive, reverse the digits
        res = parseInt(String(x).split('').reverse().join(''));
    }

    // Check if the reversed number is outside the 32-bit integer range
    if (res > Math.pow(2, 31) - 1 || res < -Math.pow(2, 31)) {
        return 0;  // Return 0 if the result is out of bounds
    }

    // Return the reversed number
    return res;    
};

Copied!

function reverse(x: number): number {
    // Convert the absolute value of x to a string, reverse it, and join back into a string
    const reversedString = Math.abs(x).toString().split('').reverse().join('')
    
    // 32-bit signed integer max value
    const int32Bit = '2147483647'

    // This is the part everyone is ignoring.
    // We can't store the value as a number before we make sure that it fits 32-bit integer size.
    if (reversedString.length === int32Bit.length) {
        // Loop through the string to compare it to the max 32-bit value
        for (let i = 0; i < reversedString.length - 1; i++) {
            if (reversedString[i] === int32Bit[i]) {
                continue  // Continue if the digits are the same
            }
            if (reversedString[i] < int32Bit[i]) {
                // If at least one of the digits is smaller, it's definitely a valid reversal
                break
            }
            if (reversedString[i] > int32Bit[i]) {
                // If any digit is greater, then it exceeds the 32-bit range, return 0
                return 0
            }
        }
    }
    
    // Now it's safe to convert the string back to a number
    const reversed = parseInt(reversedString)
    
    // Return the reversed value, considering the original sign of x
    return x > 0 ? reversed : -reversed
};

Copied!

class Solution {
    /**
     * @param Integer $x
     * @return Integer
     */
    const INT_MIN = -2147483647;  // Define the minimum value for a 32-bit signed integer
    const INT_MAX = 2147483647;  // Define the maximum value for a 32-bit signed integer

    function reverse($x) {
        // Reverse the absolute value of $x and cast it back to an integer
        $str = (int) strrev(abs($x));
        
        // If the original number was negative, make the reversed number negative
        if($x < 0)
            $str *= -1;
        
        // Check if the reversed number exceeds the 32-bit integer limits
        if($str > self::INT_MAX || $str < self::INT_MIN)
            return 0;  // Return 0 if the number is out of the 32-bit signed integer range
        
        return $str;  // Return the reversed number
    }
}

Copied!

class Solution {
    func reverse(_ x: Int) -> Int {
        var r = 0, x = x  // Initialize result variable r and copy of x
        
        // Loop while x is not zero
        while x != 0 {
            r = r * 10  // Shift r to the left by one digit (multiply by 10)
            r = r + (x % 10)  // Add the last digit of x to r
            x /= 10  // Remove the last digit from x
        }
        
        // Check if the result is out of 32-bit integer bounds
        return r < Int32.min || r > Int32.max ? 0 : r
    }
}

Copied!

class Solution {
    fun reverse(x: Int): Int {
        var result: Long = 0  // Initialize result as Long to prevent overflow during reversal
        var n = if (x > 0) x else -x  // Work with the absolute value of x

        // Loop while there are digits remaining in n
        while (n > 0) {
            val r = n % 10  // Get the last digit of n
            result = result * 10 + r  // Append the digit to the reversed number

            // Check for overflow before updating n
            if (result > Int.MAX_VALUE || result < Int.MIN_VALUE) {
                return 0  // Return 0 if result exceeds the 32-bit integer range
            }

            n = n / 10  // Remove the last digit from n
        }

        // Return the reversed number, restoring the original sign of x
        return if (x > 0) result.toInt() else -result.toInt()
    }
}

Copied!

import 'dart:ffi';
class Solution {
  int reverse(int x) {
    // Check if the number is negative
    int a = x < 0 
        ? -(int.parse((-x).toString().split('').reversed.join())) // Reverse the absolute value of x if negative
        : int.parse(x.toString().split('').reversed.join()); // Reverse the digits of x if positive
    
    // Check if the reversed value is within the 32-bit integer range
    return a >= 2147483648 || a < -2147483648 ? 0 : a; // Return 0 if overflow occurs, else return the reversed value
  }
}

Copied!

func reverse(x int) int {
    current := x
    sign := false

    // Check if the number is negative
    if current < 0 {
        sign = true
        current = abs(current)  // Convert to positive for easy manipulation
    }

    digit := current % 10  // Get the last digit of the number
    result := digit         // Start the result with the last digit
    current /= 10           // Remove the last digit

    // Loop through all digits of the number
    for current > 0 {
        digit = current % 10  // Get the next digit
        current /= 10         // Remove the digit from the number
        result *= 10          // Shift the current result left by one digit
        result += digit       // Add the new digit to the result

        // Check for overflow beyond the 32-bit integer limits
        if result > 2147483647 || result < -2147483648 { 
            return 0  // Return 0 if overflow is detected
        }
    }

    // If the number was negative, make the result negative
    if sign == true {
        result = -result
    }

    return result  // Return the reversed number
}

// Helper function to return the absolute value of a number
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Copied!

Time and Space Complexity

Time Complexity

The time complexity of the given code is dependent on the number of digits in the integer x. Since we are handling the integer digit by digit, the number of operations is linearly proportional to the number of digits. If the integer x has n digits, then the time complexity is O(n).

Space Complexity

The space complexity of the provided code is O(1). This is because we are only using a fixed amount of additional space (ans, mi, mx, y, and a few variables for control flow) regardless of the input size.

Leave a Reply