150.Reverse Integer

MediumBit Manipulation · 7/7

Problem

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit range [-2^31, 2^31 - 1], return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned) — so you must detect overflow before it happens using only int arithmetic.

Examples

Input:  x = 123
Output: 321

Input:  x = -123
Output: -321
Explanation: The sign is kept; only the digits are reversed.

Input:  x = 120
Output: 21
Explanation: The reversed number 021 has its leading zero dropped.

Input:  x = 1534236469
Output: 0
Explanation: Reversed it would be 9646324351, which is larger than 2^31 - 1 = 2147483647.

Constraints

-2^31 <= x <= 2^31 - 1

💡 Key Insight

Reverse arithmetically: repeatedly pop the last digit with x % 10 (and x /= 10), and push it onto the result with res * 10 + digit. The only danger is the push step overflowing, so check before pushing: if res > MAX / 10 (or res == MAX / 10 and digit > 7), the next push would exceed 2147483647; symmetrically for the negative bound -2147483648. Java's % keeps the sign of x, so negatives work without special-casing.

Brute Force (String Reversal)

TimeO(d) where d ≤ 10 is the number of digitsSpaceO(d) for the strings; also relies on exceptions for control flow, which is slow and frowned upon.

Intuition

Turn the number into a string, reverse its digits, put the sign back, and let Integer.parseInt tell us whether it fits: it throws NumberFormatException on overflow, which we map to 0.

Algorithm

s = Integer.toString(x); note whether it starts with '-'.
Reverse the digit part.
Prepend '-' if needed and parse with Integer.parseInt.
If parsing throws, return 0.

Visualization

x = -123  → "-123" → digits "123" → reversed "321" → "-321" → -321
x = 1534236469 → "9646324351" → parseInt throws → 0

Code

java

class Solution {
    public int reverse(int x) {
        String s = Integer.toString(x);
        boolean negative = s.charAt(0) == '-';
        String digits = negative ? s.substring(1) : s;
        String reversed = new StringBuilder(digits).reverse().toString();
        try {
            // parseInt rejects anything outside the 32-bit range
            return Integer.parseInt(negative ? "-" + reversed : reversed);
        } catch (NumberFormatException e) {
            return 0;
        }
    }
}

Complexity

Time: O(d) where d ≤ 10 is the number of digits — O(1) in practice.
Space: O(d) for the strings; also relies on exceptions for control flow, which is slow and frowned upon.

Math with a 64-bit Accumulator

TimeO(log10 |x|)SpaceO(1).

Intuition

Pop/push digits arithmetically, but accumulate into a long, which can never overflow for a 10-digit reversal. At the end, check whether the long fits in an int. This is clean and correct, but it violates the problem's "no 64-bit integers" rule — shown here as a stepping stone.

Algorithm

long res = 0.
While x != 0: res = res * 10 + x % 10; x /= 10.
If res is outside [Integer.MIN_VALUE, Integer.MAX_VALUE] return 0, else return (int) res.

Visualization

x = 120
pop 0 → res = 0
pop 2 → res = 2
pop 1 → res = 21    → fits → 21

Code

java

class Solution {
    public int reverse(int x) {
        long res = 0; // wide enough to hold any 10-digit reversal
        while (x != 0) {
            res = res * 10 + x % 10; // x % 10 is negative for negative x
            x /= 10;
        }
        if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) res;
    }
}

Complexity

Time: O(log10 |x|) — one iteration per digit (at most 10).
Space: O(1).

Pop and Push with Overflow Pre-CheckOptimal

TimeO(log10 |x|)SpaceO(1)

Intuition

Stay in int the whole time and guard each push. Before computing res * 10 + digit:

If res > MAX / 10 (214748364), then res * 10 alone overflows.
If res == MAX / 10, the push is safe only when digit <= 7 (because MAX ends in 7).
Mirror image for negatives: res < MIN / 10, or res == MIN / 10 with digit < -8 (because MIN ends in 8).

If either guard fires, return 0.

Algorithm

res = 0.
While x != 0:
- digit = x % 10; x /= 10.
- If res > MAX / 10 or (res == MAX / 10 and digit > 7), return 0.
- If res < MIN / 10 or (res == MIN / 10 and digit < -8), return 0.
- res = res * 10 + digit.
Return res.

Dry Run

flowchart TD
    A["x = -123, res = 0"] --> B["pop digit -3, x = -12<br/>safe → res = -3"]
    B --> C["pop digit -2, x = -1<br/>safe → res = -32"]
    C --> D["pop digit -1, x = 0<br/>safe → res = -321"]
    D --> E{"x == 0?"}
    E -->|"yes"| F["return -321"]

x = 1534236469
...after 9 pops: res = 964632435, next digit = 1
res > MAX / 10 = 214748364  → pushing would overflow → return 0

Code

java

class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int digit = x % 10; // keeps the sign of x
            x /= 10;
            // would res * 10 + digit exceed Integer.MAX_VALUE (2147483647)?
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) {
                return 0;
            }
            // would res * 10 + digit go below Integer.MIN_VALUE (-2147483648)?
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) {
                return 0;
            }
            res = res * 10 + digit;
        }
        return res;
    }
}

Complexity

Time: O(log10 |x|) — at most 10 iterations.
Space: O(1) — only int variables, satisfying the no-64-bit rule.

Complexity Comparison

Approach	Time	Space
String Reversal	O(d)	O(d)
64-bit Accumulator	O(log10 \|x\|)	O(1)
Pop and Push with Pre-Check	O(log10 \|x\|)	O(1)

Common Pitfalls

Checking for overflow after res * 10 + digit — in Java the value has already wrapped around silently, so the check is meaningless.
Taking Math.abs(x) first — Math.abs(Integer.MIN_VALUE) is still Integer.MIN_VALUE (it overflows), breaking the logic. Let % and / handle the sign.
Forgetting trailing zeros: 120 must become 21; the arithmetic approach handles this naturally because leading zeros contribute nothing.
Assuming x % 10 is always non-negative — in Java it takes the sign of x, which is exactly why the negative guard compares against -8.