Reverse Integer
Problem
x, return the number formed by writing
its digits in reverse order (the sign stays). If that result falls outside
[-231, 231-1], return 0. Assume you may not
store 64-bit integers.x = 123Output321x = -123Output-321x = 1534236469Output0 (overflow)-231 ≤ x ≤ 231-1 · trailing zeros vanish (120 → 21) · no 64-bit types
Try it yourself
class Solution {
public int reverse(int x) {
}
}
rev = rev * 10 + d, check whether it would
overflow by comparing rev with MAX / 10 (and MIN / 10).
Detect overflow before it happens, using only ints.Instinct Digits, factors, slopes or distances hide a formula - find the invariant, then guard against overflow, negatives and floating-point error.
Memory hack Mod peels, gcd reduces, squares compare - and long saves the day. Peel digits with %10, reduce slopes with gcd, compare squared distances.
Open the Math & Geometry guide →Approaches
Brute ForceString Reverse + Parse
O(log x)Space O(log x)Write the absolute digits to a StringBuilder, reverse them,
re-attach the sign and let Integer.parseInt decide: it throws
NumberFormatException when the value does not fit in an
int, which we map to 0.
public int reverse(int x) { String s = Integer.toString(x); boolean negative = x < 0; if (negative) s = s.substring(1); // strip '-' String r = (negative ? "-" : "") + new StringBuilder(s).reverse(); try { return Integer.parseInt(r); } catch (NumberFormatException e) { return 0; // out of 32-bit range } }
Short and safe, but uses a string and an exception for control flow.
BetterMath Reverse in a long
O(log x)Space O(1)Pop digits with x % 10 (Java keeps the sign, so negatives just
work) and push them with rev * 10 + d. A long holds any
10-digit reverse, so we check the range once at the end and cast.
public int reverse(int x) { long rev = 0; while (x != 0) { rev = rev * 10 + x % 10; x /= 10; } if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) return 0; return (int) rev; }
Clean and fast, but breaks the “no 64-bit integers” rule.
OptimalMath Reverse with Pre-Overflow Check
O(log x)Space O(1)Stay in int. rev * 10 + d exceeds
MAX = 2147483647 exactly when rev > MAX/10, or
rev == MAX/10 and d > 7. Symmetrically for
MIN = -2147483648: rev < MIN/10, or
rev == MIN/10 and d < -8. Check first, then update.
public int reverse(int x) { int rev = 0; int maxDiv10 = Integer.MAX_VALUE / 10, minDiv10 = Integer.MIN_VALUE / 10; while (x != 0) { int d = x % 10; // negative when x is negative x /= 10; if (rev > maxDiv10 || (rev == maxDiv10 && d > 7)) return 0; if (rev < minDiv10 || (rev == minDiv10 && d < -8)) return 0; rev = rev * 10 + d; } return rev; }
Dry runx = -123
- start-123x=-123, rev=0
- pop 1-12·d=-3 → rev=-3
- pop 2-1··d=-2 → rev=-32
- pop 3····d=-1 → rev=-321 ✔
Pure 32-bit arithmetic, one pass over the digits — meets every constraint.
d > 7 / d < -8 tests can never fire for a
valid 10-digit input (its leading digit is ≤ 2), but keeping them makes the
check obviously correct.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | String Reverse + Parse | O(log x) | O(log x) |
| Better | Math Reverse in a long | O(log x) | O(1) |
| Optimal | Math Reverse with Pre-Overflow Check | O(log x) | O(1) |
- Computing
rev * 10 + dfirst and checking after — the overflow already happened. - Using
Math.abs(x):abs(-2147483648)is still negative. - Returning the overflowed value instead of
0.
- Ask about the 64-bit restriction early — it rules out the
longshortcut. - Point out that Java's
%keeps the sign, so negatives need no special case. - Test the boundaries:
1534236469,-2147483648,120.