Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reverse Integer

MEDIUMProblemSolveExternal Links

Description

You are given a signed 32-bit integer x. Your task is to reverse the digits of x and return the result.

However, there is an important catch: if reversing the digits causes the value to fall outside the signed 32-bit integer range [-2^31, 2^31 - 1] (that is, [-2147483648, 2147483647]), you must return 0 instead.

Additionally, you should assume that the environment does not allow you to store 64-bit integers (signed or unsigned). This means you cannot simply reverse the number and then check if the result overflows — you must detect potential overflow before it happens.

In simpler terms: Take a number, flip its digits around. If the flipped number is too big or too small to fit in a 32-bit integer, return 0. Negative numbers stay negative after reversal, and trailing zeros in the original number become leading zeros (which are dropped).

Examples

Example 1

Input: x = 123

Output: 321

Explanation: The digits of 123 are 1, 2, and 3. Reversing them gives 3, 2, 1, which forms the number 321. Since 321 is within the 32-bit signed integer range, we return 321.

Example 2

Input: x = -123

Output: -321

Explanation: The absolute value of -123 has digits 1, 2, 3. Reversing gives 3, 2, 1, forming 321. Restoring the negative sign gives -321. Since -321 is within the valid range, we return -321.

Example 3

Input: x = 120

Output: 21

Explanation: Reversing 120 gives 021, but leading zeros are dropped, so the result is 21.

Example 4

Input: x = 1534236469

Output: 0

Explanation: Reversing gives 9646324351, which exceeds 2147483647 (the maximum 32-bit signed integer). Since it overflows, we return 0.

Constraints

  • -2^31 ≤ x ≤ 2^31 - 1
  • The environment does not allow storing 64-bit integers

Editorial

Brute Force

Intuition

The most straightforward way to reverse a number's digits is to treat it as a string. Strings are easy to reverse — you just read the characters from right to left.

Think of it like writing a number on a piece of paper. If someone asks you to reverse 123, you'd naturally read the digits backwards: 3, 2, 1 → 321. That's exactly what string reversal does.

The approach is:

  1. Convert the integer to a string
  2. Handle the negative sign separately (save it, strip it)
  3. Reverse the string of digits
  4. Convert back to an integer
  5. Check if the result fits within the 32-bit signed integer range

This works, but it sidesteps the problem's spirit. The problem says we cannot use 64-bit integers, and in many languages, converting a reversed string back to an integer might internally use a larger type. It also uses extra memory proportional to the number of digits.

Step-by-Step Explanation

Let's trace through with x = -123:

Step 1: Record the sign. x is negative, so sign = -1. Work with absolute value: 123.

Step 2: Convert 123 to string: "123".

Step 3: Reverse the string: "321".

Step 4: Convert "321" back to integer: 321.

Step 5: Restore the sign: 321 × (-1) = -321.

Step 6: Check overflow: Is -321 within [-2147483648, 2147483647]? Yes.

Step 7: Return -321.

Now let's trace with x = 1534236469 (overflow case):

Step 1: Sign = 1 (positive). Absolute value: 1534236469.

Step 2: Convert to string: "1534236469".

Step 3: Reverse string: "9646324351".

Step 4: Convert back to integer: 9646324351.

Step 5: Sign is positive, result = 9646324351.

Step 6: Check overflow: Is 9646324351 ≤ 2147483647? No — it exceeds the maximum.

Step 7: Return 0.

String Reversal Approach for x = -123 — Watch how we convert the integer to a string, reverse the character sequence, and convert back while handling the sign and checking for overflow.

Algorithm

  1. Record the sign of x (positive or negative)
  2. Convert the absolute value of x to a string
  3. Reverse the string
  4. Convert the reversed string back to an integer
  5. Restore the original sign
  6. If the result is outside [-2^31, 2^31 - 1], return 0
  7. Otherwise, return the result

Code

class Solution {
public:
    int reverse(int x) {
        int sign = (x < 0) ? -1 : 1;
        string s = to_string(abs((long long)x));
        std::reverse(s.begin(), s.end());
        
        long long result = (long long)sign * stoll(s);
        
        if (result < INT_MIN || result > INT_MAX) {
            return 0;
        }
        return (int)result;
    }
};
class Solution:
    def reverse(self, x: int) -> int:
        sign = -1 if x < 0 else 1
        reversed_str = str(abs(x))[::-1]
        result = sign * int(reversed_str)
        
        if result < -(2**31) or result > 2**31 - 1:
            return 0
        return result
class Solution {
    public int reverse(int x) {
        int sign = (x < 0) ? -1 : 1;
        String s = new StringBuilder(String.valueOf(Math.abs((long)x))).reverse().toString();
        
        long result = (long) sign * Long.parseLong(s);
        
        if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {
            return 0;
        }
        return (int) result;
    }
}

Complexity Analysis

Time Complexity: O(log₁₀(|x|))

The number of digits in x is ⌊log₁₀(|x|)⌋ + 1. Converting to string, reversing, and converting back each take time proportional to the number of digits.

Space Complexity: O(log₁₀(|x|))

We create a string representation of the number, which has as many characters as there are digits in x. This extra space is proportional to the digit count.

Why This Approach Is Not Efficient

The string conversion approach has two significant drawbacks:

1. Violates the 64-bit constraint: The problem explicitly states that we cannot store 64-bit integers. Yet, to check overflow after converting the reversed string back to a number, we need a type large enough to hold potentially overflowed values (like 9646324351 for input 1534236469). In C++ and Java, this forces us to use long long / long, which are 64-bit types. In Python, integers are arbitrary precision, so the constraint is implicitly violated.

2. Unnecessary space usage: Converting to a string allocates O(log₁₀(|x|)) extra memory. While this isn't a huge amount (at most 10 characters for a 32-bit int), a purely mathematical approach can do this with O(1) space.

The core issue: We detect overflow after it has already happened (in the converted number). The ideal approach would detect overflow before each step, working entirely within 32-bit arithmetic. We can achieve this by extracting and appending digits mathematically using modulo and division — checking at each step whether the next multiplication would cause overflow.

Optimal Approach - Mathematical Digit Extraction

Intuition

Instead of converting to a string, we can extract digits mathematically. The key insight is that x % 10 gives us the last digit, and x / 10 removes the last digit. We can "pop" digits from the end of x and "push" them onto a result variable.

Imagine you have a stack of numbered blocks arranged as the number 123. You take the bottom block (3) and place it as the first block in a new stack. Then you take the next bottom block (2) and place it next. Finally, the last block (1) goes on top. The new stack reads 321 — the number is reversed.

Mathematically:

  • Pop: digit = x % 10, then x = x / 10
  • Push: result = result × 10 + digit

The critical challenge is overflow detection. Before we do result = result × 10 + digit, we must check: will result × 10 + digit exceed the 32-bit range? We can check this before multiplying:

  • If result > INT_MAX / 10, then result × 10 will definitely overflow
  • If result < INT_MIN / 10, then result × 10 will definitely underflow
  • If result == INT_MAX / 10 and digit > 7, overflow occurs (since INT_MAX ends in 7)
  • If result == INT_MIN / 10 and digit < -8, underflow occurs (since INT_MIN ends in 8)

This way, we never actually overflow — we predict it and return 0 before it happens.

Step-by-Step Explanation

Let's trace through with x = -123:

Step 1: Initialize result = 0. The 32-bit range is [-2147483648, 2147483647].

Step 2: Iteration 1: x = -123

  • Pop digit: -123 % 10 = -3 (in C++/Java; Python needs adjustment)
  • Overflow check: Is result (0) in safe range? 0 is between -214748364 and 214748364. Safe.
  • Push digit: result = 0 × 10 + (-3) = -3
  • Remove digit: x = -123 / 10 = -12

Step 3: Iteration 2: x = -12

  • Pop digit: -12 % 10 = -2
  • Overflow check: Is result (-3) in safe range? Yes. Safe.
  • Push digit: result = -3 × 10 + (-2) = -32
  • Remove digit: x = -12 / 10 = -1

Step 4: Iteration 3: x = -1

  • Pop digit: -1 % 10 = -1
  • Overflow check: Is result (-32) in safe range? Yes. Safe.
  • Push digit: result = -32 × 10 + (-1) = -321
  • Remove digit: x = -1 / 10 = 0

Step 5: x = 0, loop ends. Return result = -321.

Now let's see how overflow detection catches a bad case with x = 1534236469:

After several iterations, result reaches 964632435 and x = 1.

  • Pop digit: 1 % 10 = 1
  • Overflow check: Is 964632435 ≤ 214748364? NO! 964632435 > 214748364.
  • If we multiplied by 10 we'd get 9646324350 which vastly exceeds 2147483647.
  • Return 0 immediately.

Mathematical Digit Extraction: Reversing x = -123 — Watch how we extract digits from the right using modulo, and build the reversed number from left to right, checking for overflow at each step before multiplying.

Algorithm

  1. Initialize result = 0
  2. While x ≠ 0:
    a. Extract the last digit: digit = x % 10
    b. Check for overflow BEFORE multiplying:
    • If result > INT_MAX / 10 or result < INT_MIN / 10, return 0
    • (For boundary equality cases: if result == INT_MAX / 10 and digit > 7, return 0; if result == INT_MIN / 10 and digit < -8, return 0)
      c. Push the digit onto result: result = result × 10 + digit
      d. Remove the last digit from x: x = x / 10 (integer division, truncating toward zero)
  3. Return result

Code

class Solution {
public:
    int reverse(int x) {
        int result = 0;
        
        while (x != 0) {
            int digit = x % 10;
            
            // Check overflow before multiplying
            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;
            x /= 10;
        }
        
        return result;
    }
};
class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -(2**31), 2**31 - 1
        result = 0
        
        while x != 0:
            # Python's modulo returns positive for negative x, so adjust
            digit = x % 10
            if x < 0 and digit > 0:
                digit -= 10
            
            # Check overflow before multiplying
            if result > INT_MAX // 10 or result < INT_MIN // 10 + 1:
                return 0
            
            result = result * 10 + digit
            x = (x - digit) // 10
        
        return result
class Solution {
    public int reverse(int x) {
        int result = 0;
        
        while (x != 0) {
            int digit = x % 10;
            
            // Check overflow before multiplying
            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;
            x /= 10;
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log₁₀(|x|))

The while loop runs once per digit of x. A 32-bit integer has at most 10 digits, so the loop runs at most 10 times. Each iteration performs constant-time arithmetic operations (modulo, division, multiplication, comparison). Formally, the number of digits is ⌊log₁₀(|x|)⌋ + 1.

Space Complexity: O(1)

We use only a fixed number of integer variables (result, digit). No additional data structures are allocated, and no recursion is used. The space consumption does not grow with the size of the input.