MEDIUM
MATHEMATICS

How to solve the Reverse Integer Problem

STRINGS
Written By
tom-wagner.png
Tom Wagner
Ajith Jose

Introduction Reverse Integer

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.

Problem Reverse Integer

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 Inputs and Outputs

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

Solution Reverse Integer

Watch Someone Solve Reverse Integer
FireEye InterviewJava Interview
Advance this person to the next round?
Thumbs up
Technical Skills:
3/4
Problem Solving Ability:
3/4
Communication Ability:
3/4
Show Transcript

Reverse Signed Integer Approaches

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 input integer to string
  2. Reverse the string
  3. Convert 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 Questions Similar to Reverse Integer

MEDIUM
Data Structures and Algorithms
Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

Watch 1 interview
MEDIUM
Data Structures and Algorithms
Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

Watch 1 interview
EASY
Data Structures and Algorithms
Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

Watch 2 interviews

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.