MEDIUM
MATHEMATICS

# How to Solve the Reverse Integer Problem

Written By Tom Wagner Ajith Jose

## How to Reverse an Integer: Overview

The Reverse Integer problem offers a straightforward task of taking an integer as input and returning the reverse representation of that integer. This problem can be solved naively, not unlike reversing a string, but also invites a more challenging mathematical approach, especially when considering edge cases such as handling negative numbers and overflow cases.

## 3 Examples of the Reverse Integer Interview Question

Given a 32-bit signed integer `x`, reverse digits of the integer. If reversing the integer causes the value to go outside the signed 32-bit integer range [-2³¹, 2³¹ - 1], then return 0.

### Example 1#

Input: x = 123 Output: 321

### Example 2

Input: x = -123 Output: -321

### Example 3

Input: x = 1563847412 Output: 0 since reversing the integer would make it greater than integer max (2147483651 > 2147483647)

Constraints

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

## How to Reverse an Integer (with Solutions in Java & Python)

Below we walk through two different ways to reverse an integer both using a reverse signed integer approach.

### 1. String Conversion Approach

When tackling an algorithms problem one good place to start is by thinking about what you would do if you were solving the problem manually, and for this problem that approach is fairly straightforward. For example, if I were tasked with reversing the integer `321`, I would flip/reverse the integer and then double-check to make sure the answer is within the 32-bit integer range.

We can translate this approach to code by taking the following steps:

1. Convert the input integer to a string
2. Reverse the string
3. Convert the reversed string back to a number
4. If the number is within 32-bit range, return `0`, otherwise return the number

#### Reverse Signed Integer Java and Python Solutions - String Conversion Approach

``````class Solution {
public int reverse(int x) {

boolean is_negative = x < 0;

// convert input integer to string
String x_string = String.valueOf(x);
if(x_string.charAt(0) == '-') {
x_string = x_string.substring(1);
}

// reverse the converted string
StringBuilder sb = new StringBuilder(x_string);
String reversed_x_string = sb.reverse().toString();
reversed_x_string = (is_negative ? '-'+reversed_x_string : reversed_x_string);

// convert the reversed string back to a long number
long reversed_number = Long.parseLong(reversed_x_string);

// return 0 if the reversed number is not within 32-bit integer range
if(reversed_number > Integer.MAX_VALUE || reversed_number < Integer.MIN_VALUE) {
return 0;
}

// return integer version of the number otherwise
return (int) reversed_number;
}
}
``````

#### Time/Space Complexity

• Time Complexity: `O(log(x))`. The string / number conversions and reversals in this approach result in one iteration over the number of digits of the input number.

If you apply `log` to the base 10 on the input number, you get the number of digits in the input number. So, the worst case time complexity is `O(log(x))`, where `x` is the input number.

• Space Complexity: `O(log(x))`, we utilize an additional string with size equivalent to the number of digits in the input number.

### 2. Math Approach

The least significant digit of an integer can be obtained by performing a mod operation over 10. To retrieve all digits of the number except the last one, you can perform integer division by 10. You can continue to perform the mod operation on the remaining digits (until it returns zero) to capture all digits of the integer.

We will be building the result as we go and storing intermediate values in a variable named `reversed_integer`.

``````last_digit = x % 10

x /= 10

reversed_integer = reversed_integer x 10 + last_digit
``````

Also note that the same approach can be applied to negative integers without issues. In order to use the same approach for negative numbers, we can take the absolute value of the initial integer `x` and negate the result at the end.

Example: Initial values

``````x = 123
reversed_integer = 0
``````

Iteration 1:

``````last_digit = 123 % 10 = 3
x = 123 / 10 = 12
reversed_integer = 0 x 10 + 3 = 3
``````

Iteration 2:

``````last_digit = 12 % 10 = 2
x = 12 / 10 = 1
reversed_integer = 3 x 10 + 2 = 32
``````

Iteration 3:

``````last_digit = 1 % 10 = 1
x = 1 / 10 = 0
reversed_integer = 32 x 10 + 1 = 321
``````

However, applying this math could also lead us to cases where the reversed integer is not within the 32-bit integer range.

Example Case 1:

``````x = 1663847412
reversed_integer = 2147483661 which is greater than 2147483647 (i.e, integer max value = 2^31 -1)
``````

Example Case 2:

``````x = 8463847412
reversed_integer = 2147483648 > 2147483647
``````

Based on the above example cases, `reversed_integer` is not within the 32-bit integer range if one of the below conditions are satisfied.

1. `reversed_integer > integer_max / 10`
2. `reversed_integer == integer_max / 10 AND x > integer_max % 10`

For the second case here, the input `x` values possible are only 8463847412 and 9463847412.

``````x = 8463847412
reversed_integer = 2147483648 > 2147483647
``````
``````x = 9463847412
reversed_integer = 2147483649 > 2147483647
``````

However, both of these numbers are not valid integer inputs and so the second condition is not necessary.

### Reverse Signed Integer Java and Python Solutions - Math Approach

``````class Solution {
public int reverse(int x) {

int ans = 0;
boolean isNegative = x < 0;

// Take absolute value
x = Math.abs(x);

while(x > 0) {

// Compare current answer with Integer MAX value (i.e, the maximum 32-bit integer value) without the least significant digit
if(ans > Integer.MAX_VALUE / 10) {
return 0;
}

// Deduce the reversed integer mathematically
ans = ans * 10 + x % 10;
x /= 10;
}

// Negate the answer if input is negative
return isNegative ? -ans : ans;
}
}
``````

#### Time/Space Complexity

• Time Complexity: `O(log(x))`, for the same reason as Approach 1. The while loop in this solution iterates over all the digits in the input number and if `x` is the input number, `log(x)` to the base 10 would give us the number of digits in the number. Therefore, `O(log(x))` would be the effective time complexity of the solution.
• Space Complexity: `O(1)`

## Practice the Reverse Integer Problem With Our AI Interviewer

Start AI Interview