Reverse Integer

Platform: LeetCode
Difficulty Level: Medium
Link: reverse integer

Problem

Input

• x: 32-bit signed integer

Goal

• Reverse the digits of the integer x.
• reversed x should be in the signed 32-bit range [-2^31, 2^31 - 1].
• Return 0 if reversed x is not in the range.

Assumptions

Examples

Example 1:

Input: x = 123

Output: 321

Example 2:

Input: x = -123

Output: -321

Example 3:

Input: x = 120

Output: 21

Solutions

Approach 1: String Conversion

The most naive or the bruteforce approach is string conversion.

1. Get the absolute integer of x (remove the negative sign bit)
2. Convert absolute integer to string
3. Reverse the string
4. Convert the reversed string back to integer
5. If x was negative, attach the negative sign bit to the reversed integer
6. Check if the reversed integer is in signed 32-bit range

Code

class Solution:
    def reverse(self, x: int) -> int:
        INT32_MIN = -2**31
        INT32_MAX = 2**31 - 1

        sign = -1 if x < 0 else 1
        
        x_abs = abs(x)
        x_str = str(x_abs)
        x_str_rev = x_str[::-1]
        x_int_rev = int(x_str_rev)

        x_int_rev = x_int_rev * sign
        
        if INT32_MIN <= x_int_rev <= INT32_MAX:
            return x_int_rev
        
        return 0

func reverse(x int) int {
    sign := 1
	if x < 0 {
		sign = -1
		x = -x
	}

	x_str := strconv.Itoa(x)
	x_str_rev := []rune(x_str)
	slices.Reverse(x_str_rev)
	x_int_rev, _ := strconv.Atoi(string(x_str_rev))

	x_int_rev = x_int_rev * sign

	if math.MinInt32 <= x_int_rev && x_int_rev <= math.MaxInt32 {
		return x_int_rev
	}

	return 0
}

Complexity Analysis

Let n be the number,

Time

• int to string conversion = $O(log_{10}(n))$
• reverse string = $O(log_{10}(n))$
• string to int conversion = $O(log_{10}(n))$

Time = $O(log_{10}(n))$

Space

• string representation = $O(log_{10}(n))$
• reversed string = $O(log_{10}(n))$

Space = $O(log_{10}(n))$

Comments

• The assumption is the environment does not allow us to store 64-bit signed or unsigned integers. But in this approach, we are first building the reversed integer and then checking whether it is in 32-bit range. Though the solution is accepted by LeetCode, but it violates the assumption.
• Since we are converting the integer to string, it introduces additional space complexity.

Approach 2: modulo and division

The efficient math way to reverse the integer is to strip the digits one by one using modulo and division approach.

For example, consider x = 123.
We want to build reverse of x i.e. 321.

1. Extracting the last digit
   We can get the digit at ones place using modulo operation. Modulo will give the remainder of the division.

   x % 10
   123 % 10 = 3

2. Strip off the last digit from x
   Remove the last digit from x using floor division.

   x = x // 10
   x = 123 // 10 = 12

3. Repeat the above steps

   12 % 10 = 2
   12 // 10 = 1
   
   1 % 10 = 1
   1 // 10 = 0

4. Building the reversed number, digit by digit

   reversed = 0
   
   reversed = reversed * 10 + 3 = 3
   reversed = reversed * 10 + 2 = 30 + 2 = 32
   reversed = reversed * 10 + 1 = 320 + 1 = 321

So for each digit we perform below 3 operations:

digit = x % 10
x = x // 10
reversed = reversed * 10 + digit

Additionally, we also want to make sure that we don’t exceed the signed or unsigned 32-bit range. We want to check this condition before constructing the number to avoid overflow error.

For every digit that we append to the reversed number, before appending we want to ensure that it will not exceed the specified signed or unsigned 32-bit range. In simple words, the below condition should be satisfied.

INT32_MIN <= reversed * 10 + digit <= INT32_MAX
-2,147,483,648 <= reversed * 10 + digit <= 2,147,483,647

The challenge is we need to check this condition without computing the number. We need to look at the above condition from a different perspective.

Since we want to check the range before appending the number, we strip one digit from the INT32_MAX.

INT32_MAX // 10 = 2,147,483,64

Before appending the new digit, this will be our limit.

1. Inside the boundary

   reversed = 2,147,483,63
   digit = 9
   
   reversed < 2,147,483,64
   
   reversed = reversed * 10 + digit = 2,147,483,639 < INT32_MAX ---> allowed

   So appending any digit will always be inside the boundary.

2. At the boundary

   reversed = 2,147,483,64
   digit = 7
   
   reversed == 2,147,483,64
   
   reversed = reversed * 10 + digit =  2,147,483,647 == INT32_MAX ---> allowed

   When reversed == INT32_MAX // 10 and digit == 7, we are at the boundary.

3. Overflow

   reversed = 2,147,483,64
   digit = 8
   
   reversed == 2,147,483,64
   
   reversed = reversed * 10 + digit = 2,147,483,648 > INT32_MAX ---> overflow

   When reversed == INT32_MAX // 10 and digit > 7, the number overflows.

From the observations of the above example, the condition for overflow would be:

if reverse > INT32_MAX // 10 or (reversed == INT32_MAX // 10 and digit > 7):
    return 0

Now, if x is negative, we don’t need to explicitly check for the INT32_MIN overflow, instead we can get the absolute of x and only check for the positive scenario. Because if positive of x is in the range, then negative of x will also be in the range. So we handle sign seperately.

Code

class Solution:
    def reverse(self, x: int) -> int:
        INT32_MIN = -2**31
        INT32_MAX = 2**31 - 1

        sign = -1 if x < 0 else 1
        
        number = abs(x)
        reversed_number = 0

        while number != 0:
            digit = number % 10
            number = number // 10

            # check for overflow before computing the number
            if reversed_number > INT32_MAX // 10 or (reversed_number == INT32_MAX // 10 and digit > 7):
                return 0
            
            reversed_number = reversed_number * 10 + digit
        
        return reversed_number * sign

func reverse(x int) int {
    number := x
    sign := 1

    if x < 0 {
        sign = -1
        number = -x // abs of number
    }

    reversed_number := 0

    for number != 0 {
        digit := number % 10
        number = number / 10 // floor division

        // check for overflow before computing the number
        if reversed_number > math.MaxInt32 / 10 || (reversed_number == math.MaxInt32 / 10 && digit > 7) {
            return 0
        }

        reversed_number = reversed_number * 10 + digit
    }

    return reversed_number * sign
}

Complexity Analysis

Let n be the number,

Time

• traversing each digit once in number = $O(log_{10}(n))$

Time = $O(log_{10}(n))$

Space

• no extra space used

Space = $O(1)$

Comments

• The assumption that the environment does not allow us to store signed or unsigned 64-bit numbers is now satisfied. We are checking if the number is in signed or unsigned 32-bit range before computing the number to prevent overflow error.
• Compared to the string conversion approach, this approach is efficient in terms of space.