How to Solve Reverse Integer
Reverse Integer Introduction
Reverse Integer Introduction
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.
Reverse Integer Problem
Reverse Integer Problem
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
Practice the Reverse Integer Problem With Our AI Interviewer
Practice the Reverse Integer Problem With Our AI Interviewer
Reverse Integer Solutions
Reverse Integer Solutions
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:
- Convert the input integer to a string
- Reverse the string
- Convert the reversed string back to a number
- 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;
}
}
1class Solution {
2 public int reverse(int x) {
3
4 boolean is_negative = x < 0;
5
6 // convert input integer to string
7 String x_string = String.valueOf(x);
8 if(x_string.charAt(0) == '-') {
9 x_string = x_string.substring(1);
10 }
11
12 // reverse the converted string
13 StringBuilder sb = new StringBuilder(x_string);
14 String reversed_x_string = sb.reverse().toString();
15 reversed_x_string = (is_negative ? '-'+reversed_x_string : reversed_x_string);
16
17 // convert the reversed string back to a long number
18 long reversed_number = Long.parseLong(reversed_x_string);
19
20 // return 0 if the reversed number is not within 32-bit integer range
21 if(reversed_number > Integer.MAX_VALUE || reversed_number < Integer.MIN_VALUE) {
22 return 0;
23 }
24
25 // return integer version of the number otherwise
26 return (int) reversed_number;
27 }
28}
29Time/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.
reversed_integer > integer_max / 10reversed_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;
}
}
1class Solution {
2 public int reverse(int x) {
3
4 int ans = 0;
5 boolean isNegative = x < 0;
6
7 // Take absolute value
8 x = Math.abs(x);
9
10 while(x > 0) {
11
12 // Compare current answer with Integer MAX value (i.e, the maximum 32-bit integer value) without the least significant digit
13 if(ans > Integer.MAX_VALUE / 10) {
14 return 0;
15 }
16
17 // Deduce the reversed integer mathematically
18 ans = ans * 10 + x % 10;
19 x /= 10;
20 }
21
22 // Negate the answer if input is negative
23 return isNegative ? -ans : ans;
24 }
25}
26Time/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 ifxis 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)
Watch Mock Interviews Featuring the Reverse Integer Question
Practice Questions Similar to Reverse Integer
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.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
