How to Solve the Reverse Integer Problem

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

Java

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.

• 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.

Reverse Signed Integer Java and Python Solutions - Math Approach

Java

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.
• Space Complexity: O(1).

Practice the Reverse Integer Problem With Our AI Interviewer

Watch These Related Mock Interviews

FireEye Interviewer
Three sum
Warp Dromedary,aFireEyeengineer, interviewed in Java
Watch interview