MEDIUM

MATHEMATICS

STRINGS

Written By

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.

**Input:** x = 123
**Output:** 321

**Input:** x = -123
**Output:** -321

**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?

Technical Skills:

3/4

Problem Solving Ability:

3/4

Communication Ability:

3/4

Show Transcript

Watch more mock interviews

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 input integer to string
- Reverse the string
- Convert reversed string back to a number
- If the number is within 32-bit range, return
`0`

, otherwise return the number

```
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}
29
```

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

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 / 10`

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

```
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}
26
```

- 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)`

MEDIUM

Data Structures and Algorithms

Build a Max Heap

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

HEAPSTREES

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.

ARRAYSSORTINGHASH MAPSSEARCH

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.

LINKED LISTS

Watch 2 interviews

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.