Reverse Integer
Reverse Integer is a medium arrays & hashing problem solved with the math / number theory pattern.
The best approach, optimal (pop digits with overflow guard), runs in O(d) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (string reversal) up.
Problem
You are given a signed 32-bit integer x. Return the number you get by writing the digits of x in reverse order, keeping its sign.
If the reversed value falls outside the signed 32-bit range [-2^31, 2^31 - 1], return 0 instead. Assume the environment cannot store 64-bit integers, so the overflow has to be detected before it happens.
Examples
Example 1
- Input
x = 4073- Output
3704- Why
- The digits 4, 0, 7, 3 read backwards give 3704.
Example 2
- Input
x = -560- Output
-65- Why
- The sign stays in front and the trailing zero becomes a leading zero, which disappears.
Example 3
- Input
x = 1999999999- Output
0- Why
- Reversed it would be 9999999991, which does not fit in a signed 32-bit integer, so the answer is 0.
Constraints
-2^31 <= x <= 2^31 - 1- You may only use 32-bit integer arithmetic in the optimal approach (no 64-bit values).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (string reversal) | O(d) | O(d) |
| Optimal (pop digits with overflow guard) | O(d) | O(1) |
1Brute force (string reversal)
O(d)d is the number of digits (at most 10); each one is copied and reversed once.O(d)The string holds the d digits.Turn the absolute value into a string, reverse it, parse it as a 64-bit number, put the sign back and check whether it still fits in 32 bits. Simple, but it relies on a wider integer type.
- Take the absolute value of x as a 64-bit number and convert it to a string.
- Reverse the string and parse it back into a 64-bit number.
- Apply the original sign.
- If the value is outside [-2^31, 2^31 - 1], return 0; otherwise return it.
class Solution {
public int reverse(int x) {
long abs = Math.abs((long) x);
String rev = new StringBuilder(Long.toString(abs)).reverse().toString();
long value = Long.parseLong(rev);
if (x < 0) value = -value;
if (value < Integer.MIN_VALUE || value > Integer.MAX_VALUE) return 0;
return (int) value;
}
}class Solution:
def reverse(self, x: int) -> int:
value = int(str(abs(x))[::-1])
if x < 0:
value = -value
if value < -2**31 or value > 2**31 - 1:
return 0
return valueclass Solution {
public:
int reverse(int x) {
long long a = llabs((long long)x);
string s = to_string(a);
std::reverse(s.begin(), s.end());
long long value = stoll(s);
if (x < 0) value = -value;
if (value < INT_MIN || value > INT_MAX) return 0;
return (int)value;
}
};function reverse(x) {
const rev = String(Math.abs(x)).split('').reverse().join('');
let value = Number(rev);
if (x < 0) value = -value;
if (value < -2147483648 || value > 2147483647) return 0;
return value;
}2Optimal (pop digits with overflow guard)
O(d)One loop iteration per digit, and an int has at most 10 digits.O(1)Only a few integer variables.Peel off the last digit with % 10 and push it onto the result with result * 10 + digit. Before every push, check whether the multiplication would cross the 32-bit limits; if it would, the answer is 0. In Java the remainder keeps the sign of x, so negative numbers work without special handling.
- Set result = 0.
- While x != 0: digit = x % 10, x = x / 10.
- If result > MAX / 10, or result == MAX / 10 and digit > 7, return 0.
- If result < MIN / 10, or result == MIN / 10 and digit < -8, return 0.
- result = result * 10 + digit.
- Return result.
class Solution {
public int reverse(int x) {
int result = 0;
while (x != 0) {
int digit = x % 10;
x /= 10;
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
result = result * 10 + digit;
}
return result;
}
}class Solution:
def reverse(self, x: int) -> int:
# Python's % and // round toward -infinity, so work on |x| and restore the sign
sign = -1 if x < 0 else 1
x = abs(x)
limit = 2**31 // 10 # 214748364
last = 7 if sign > 0 else 8 # largest allowed final digit
result = 0
while x != 0:
digit = x % 10
x //= 10
if result > limit or (result == limit and digit > last):
return 0
result = result * 10 + digit
return sign * resultclass Solution {
public:
int reverse(int x) {
int result = 0;
while (x != 0) {
int digit = x % 10;
x /= 10;
if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) return 0;
if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) return 0;
result = result * 10 + digit;
}
return result;
}
};function reverse(x) {
const MAX = 2147483647, MIN = -2147483648;
let result = 0;
while (x !== 0) {
const digit = x % 10;
x = Math.trunc(x / 10);
if (result > Math.trunc(MAX / 10) || (result === Math.trunc(MAX / 10) && digit > 7)) return 0;
if (result < Math.trunc(MIN / 10) || (result === Math.trunc(MIN / 10) && digit < -8)) return 0;
result = result * 10 + digit;
}
return result;
}Edge cases to test
- x = 0
- Trailing zeros, like 1200, which reverse to 21
- Negative numbers keep their sign
- Results that overflow just above 2^31 - 1 or just below -2^31
- x = -2^31 itself (its absolute value does not fit in an int)
Hints
Hint 1
x % 10 gives the last digit and x / 10 drops it. Build the answer one digit at a time.
Hint 2
Before doing result * 10 + digit, check whether that step would leave the 32-bit range.
Hint 3
Compare result against Integer.MAX_VALUE / 10 and Integer.MIN_VALUE / 10 to detect overflow before it happens.
FAQ
What is the best time complexity for Reverse Integer?
Optimal (pop digits with overflow guard) runs in O(d) time and O(1) extra space. One loop iteration per digit, and an int has at most 10 digits.
Which pattern does Reverse Integer use?
It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.
Is there a brute force solution for Reverse Integer?
Yes. Brute force (string reversal) takes O(d) time and O(d) space. Turn the absolute value into a string, reverse it, parse it as a 64-bit number, put the sign back and check whether it still fits in 32 bits.
Which edge cases should I test for Reverse Integer?
x = 0; Trailing zeros, like 1200, which reverse to 21; Negative numbers keep their sign; Results that overflow just above 2^31 - 1 or just below -2^31; x = -2^31 itself (its absolute value does not fit in an int).