Free lesson · DSA Mastery - Interview Prep, End to End

Reverse Integer

Hard5 min readdsamaths-geometry

Reverse Integer

Reverse Integer asks to reverse the digits of a signed 32-bit integer, returning 0 if the result overflows. The challenge isn't reversing - it's detecting overflow before it happens. Two clean techniques: (a) use long for intermediate values and check the int range at the end, or (b) check before each digit append whether the next operation would overflow. It demonstrates defensive integer arithmetic with overflow detection, a key habit in low-level numeric code. We present the pre-overflow-check approach (canonical).

The insight: reversing uses the same r = r * 10 + x % 10 digit-prepending pattern as Palindrome Number. The trick is the overflow check before updating r: if r > INT_MAX / 10, then r * 10 would already overflow; if r == INT_MAX / 10, then r * 10 + next_digit overflows iff next_digit > 7 (since INT_MAX ends in 7). Symmetric check on the negative side using INT_MIN / 10 and remainder -8.

The 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 integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input:  x = 123
Output: 321

Example 2:

Input:  x = -123
Output: -321

Example 3:

Input:  x = 120
Output: 21

Explanation: Reversing 120 gives 021, which is 21 (leading zeros discarded).

Constraints:

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

Approaches Overview

Standard digit-reversal loop with overflow guard before each update:

• pop = x % 10; x /= 10.
• If r > INT_MAX / 10 || (r == INT_MAX / 10 && pop > 7): return 0.
• If r < INT_MIN / 10 || (r == INT_MIN / 10 && pop < -8): return 0.
• r = r * 10 + pop.

Java's % and / on negative ints work cleanly toward zero (-123 % 10 == -3).

Approach: Pre-Overflow-Check - Canonical

The Idea

Detect overflow before it happens. INT_MAX is 2147483647 (ends in 7); INT_MIN is -2147483648 (ends in -8 when computed via Java's truncated mod). The pre-check covers both bounds without ever exceeding int range.

Logic Flowchart

graph TD
    A["r = 0"] --> B["while x != 0:"]
    B --> C["pop = x % 10; x /= 10"]
    C --> D{"r > INT_MAX/10 OR (r == INT_MAX/10 AND pop > 7)?"}
    D -->|Yes| E["return 0"]
    D -->|No| F{"r < INT_MIN/10 OR (r == INT_MIN/10 AND pop < -8)?"}
    F -->|Yes| E
    F -->|No| G["r = r * 10 + pop"]
    G --> B
    B --> H["return r"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Reverse Integer with pre-overflow checks at both positive and negative bounds before each multiply-and-add update.

Code

public static int reverse(int x) {
    int r = 0;
    while (x != 0) {
        int pop = x % 10;
        x /= 10;
        if (r > Integer.MAX_VALUE / 10 || (r == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
        if (r < Integer.MIN_VALUE / 10 || (r == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
        r = r * 10 + pop;
    }
    return r;
}

// Usage:
// reverse(123)        -> 321
// reverse(-123)       -> -321
// reverse(120)        -> 21
// reverse(1534236469) -> 0   (reversed would be 9646324351, overflows)

This Java code reverses a 32-bit integer with explicit pre-overflow checks at both bounds, returning 0 on overflow.

Step-by-Step Walkthrough

Tracing reverse(123):

graph LR
    F0["r=0, x=123; iter 1: pop=3, x=12; checks pass; r=0*10+3=3"]
    F1["iter 2: pop=2, x=1; checks pass; r=3*10+2=32"]
    F2["iter 3: pop=1, x=0; checks pass; r=32*10+1=321"]
    F3["x=0; loop ends; return 321"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough reverses 123 to 321 with three digit-extraction and prepend steps, no overflow checks failing.

Result: 321.

Complexity

Time: O(d) where d ≤ 10. Space: O(1).

Complexity Comparison

The pre-overflow check respects the problem's "no 64-bit integers" constraint while keeping the code clean.

Variations & Follow-ups

Why are the boundary digits 7 and -8?

INT_MAX = 2147483647 ends in 7. If r == INT_MAX / 10 = 214748364 and we want to append digit d to get r · 10 + d, the result fits in int iff r · 10 + d ≤ INT_MAX = 2147483647, i.e., iff d ≤ 7 (since r · 10 = 2147483640).

INT_MIN = -2147483648 ends in -8 (Java's truncated mod gives -8 for INT_MIN % 10). Symmetrically, r == INT_MIN / 10 = -214748364 and r · 10 + d requires d ≥ -8.

Why does Java's % work for negatives?

Java uses truncated division: (-123) / 10 = -12 (toward zero), and (-123) % 10 = -3 (sign of dividend). So x % 10 gives the last digit with the correct sign; we don't need to special-case negatives. (Python uses floor division - different semantics; same algorithm needs explicit sign handling there.)

What if 64-bit integers WERE allowed?

Then the simpler approach: accumulate in long, then check if result fits in int.

public static int reverse64(int x) {
    long r = 0;
    while (x != 0) {
        r = r * 10 + x % 10;
        x /= 10;
    }
    return (r < Integer.MIN_VALUE || r > Integer.MAX_VALUE) ? 0 : (int) r;
}

Equivalent semantically; just shifts the overflow check to the end. The general lesson: when the environment allows wider integers, defer overflow checks to the end; when it doesn't, check at every step.

What about the 120 → 21 case (leading zeros discarded)?

The algorithm handles it naturally: 120 has pop = 0 first, then pop = 2, then pop = 1. The result is 0 · 100 + 2 · 10 + 1 · 1 = 21. Leading zeros are implicit in the multiplicative buildup - never explicitly stored.

What about edge cases?

• x = 0: Loop never enters; return 0.
• x = INT_MIN (-2147483648): Its reverse 8463847412 overflows; return 0.
• x = INT_MAX (2147483647): Reverse 7463847412 overflows; return 0.
• Single-digit input: Returns the same digit.

Common Interview Pitfalls

• Computing r * 10 + pop first, then checking. Already overflowed - undefined behavior in C/C++, wrap-around in Java. Check first.
• Forgetting negative-side overflow check. Many implementations only check positive; negatives like -2147483648 get missed.
• Using (int) Math.abs(x) to convert. Math.abs(INT_MIN) == INT_MIN (overflow!); use sign-preserving arithmetic instead.
• Trying string reversal. Works but is verbose and slower than direct arithmetic; doesn't naturally fit the "no 64-bit" constraint.

Why This Topic Matters

Reverse Integer teaches defensive overflow detection in fixed-width integer arithmetic. The pre-check pattern (if r > MAX/10 || (r == MAX/10 && pop > 7)) is the standard idiom across low-level numeric code, embedded systems, and compiler internals. The technique generalizes to any operation prone to overflow: addition (if a > MAX - b), multiplication (if a > MAX / b), etc.

The next topic, Factorial Trailing Zeroes, asks for the number of trailing zeros in n!. Naive computation overflows immediately for n ≥ 21. The elegant solution counts pairs of factors (2, 5) in n!. Since 2's are far more abundant than 5's, the count of 5's is the limiting factor. Counting 5's = n / 5 + n / 25 + n / 125 + ... (Legendre's formula). It's a beautiful number-theory exercise that bypasses the actual factorial entirely.

Back to DSA Mastery - Interview Prep, End to End