LeetCode 7: Reverse Integer

Problem Statement

LeetCode 7, Reverse Integer, is a medium-level challenge where you take a 32-bit signed integer x and return it with its digits reversed. If reversing causes the number to go beyond the 32-bit signed integer range (from -2³¹ to 2³¹ - 1, or roughly -2.1 billion to 2.1 billion), return 0. The task is to flip the digits—like turning 123 into 321—and handle edge cases like negatives and overflow.

Constraints

  • -2³¹ <= x <= 2³¹ - 1: Input is a 32-bit signed integer (-2,147,483,648 to 2,147,483,647).
  • Output must fit within the same 32-bit signed range, or return 0 if it doesn’t.

Example

Input: x = 123
Output: 321
Explanation: Reverse 123 to get 321, which fits in the range.

Input: x = -123
Output: -321
Explanation: Reverse 123 to 321, keep the negative sign, so -321.

Input: x = 120
Output: 21
Explanation: Reverse 120 to 021, drop the leading zero, get 21.

Input: x = 0
Output: 0
Explanation: Reverse of 0 is 0.

Understanding the Problem

Imagine a number like 123. Reversing it means rewriting it as 321—starting from the last digit (3), then the middle (2), then the first (1). For -123, we reverse the digits (321) and keep the minus sign (-321). We need to:

  • Handle the sign separately.
  • Reverse the digits of the absolute value.
  • Check if the result stays within the 32-bit signed integer limits (-2,147,483,648 to 2,147,483,647), returning 0 if it overflows.

We’ll focus on:

  • Mathematical Approach: Build the reversed number digit by digit.

Solution: Mathematical Approach

Explanation

This method uses math to pull digits off the number one by one and build the reversed number step by step. We handle the sign first, work with the positive part, and check for overflow at the end.

  1. Handle Sign.
  • Save the sign of the number and work with its absolute value.

2. Reverse Digits.

  • Use division and modulo to extract digits from right to left, building the new number.

3. Check Overflow.

  • Ensure the result fits within 32-bit signed integer bounds; if not, return 0.

4. Apply Sign and Return.

  • Add the original sign back and return the result.

Step-by-Step Example

Example 1: x = 123

We have the number 123 and want to reverse it to 321.

  • Goal: Flip the digits of 123 to get 321.
  • Result for reference: 321, which is less than 2,147,483,647, so it’s valid.
  • Start: Set up a result variable at 0.
  • Step 1: Check the sign.
    • 123 is positive, so sign is +1 (we’ll multiply at the end). Work with 123.
  • Step 2: Get the last digit (3).
    • Divide 123 by 10: 123 ÷ 10 = 12 remainder 3 (or 123 % 10 = 3).
    • Add 3 to result: result = 0 * 10 + 3 = 3.
    • Update number: 123 ÷ 10 = 12 (integer division).
  • Step 3: Get the next digit (2).
    • 12 ÷ 10 = 1 remainder 2 (12 % 10 = 2).
    • Add 2 to result: result = 3 * 10 + 2 = 32.
    • Update number: 12 ÷ 10 = 1.
  • Step 4: Get the last digit (1).
    • 1 ÷ 10 = 0 remainder 1 (1 % 10 = 1).
    • Add 1 to result: result = 32 * 10 + 1 = 321.
    • Update number: 1 ÷ 10 = 0.
  • Step 5: Number is 0, stop reversing.
    • Result is 321.
  • Step 6: Check overflow.
    • 321 is between -2,147,483,648 and 2,147,483,647, so it’s fine.
  • Step 7: Apply sign.
    • Sign is +1, so 321 * 1 = 321.
  • Finish: Return 321.
    • Matches the reversed number.

Example 2: x = -123

Now, the number is -123, and we want -321.

  • Goal: Reverse 123 to 321 and keep the negative sign.
  • Result for reference: -321, within bounds.
  • Start: Result at 0.
  • Step 1: Check the sign.
    • -123 is negative, sign is -1. Work with 123 (absolute value).
  • Step 2: Last digit (3).
    • 123 % 10 = 3.
    • Result = 0 * 10 + 3 = 3.
    • Number = 123 ÷ 10 = 12.
  • Step 3: Next digit (2).
    • 12 % 10 = 2.
    • Result = 3 * 10 + 2 = 32.
    • Number = 12 ÷ 10 = 1.
  • Step 4: Last digit (1).
    • 1 % 10 = 1.
    • Result = 32 * 10 + 1 = 321.
    • Number = 1 ÷ 10 = 0.
  • Step 5: Number is 0, stop.
    • Result is 321.
  • Step 6: Check overflow.
    • 321 fits within bounds.
  • Step 7: Apply sign.
    • Sign is -1, so 321 * -1 = -321.
  • Finish: Return -321.
    • Correctly reversed with the negative sign.

Example 3: x = 120

For 120, we want 21 (dropping the leading zero).

  • Goal: Reverse 120 to get 021, then 21.
  • Result for reference: 21, within bounds.
  • Start: Result at 0.
  • Step 1: Sign is +1, work with 120.
  • Step 2: Last digit (0).
    • 120 % 10 = 0.
    • Result = 0 * 10 + 0 = 0.
    • Number = 120 ÷ 10 = 12.
  • Step 3: Next digit (2).
    • 12 % 10 = 2.
    • Result = 0 * 10 + 2 = 2.
    • Number = 12 ÷ 10 = 1.
  • Step 4: Last digit (1).
    • 1 % 10 = 1.
    • Result = 2 * 10 + 1 = 21.
    • Number = 1 ÷ 10 = 0.
  • Step 5: Number is 0, stop.
    • Result is 21 (leading zero drops naturally).
  • Step 6: Check overflow.
    • 21 is fine.
  • Step 7: Sign is +1, so 21 * 1 = 21.
  • Finish: Return 21.
    • Matches the reversed number.

Code

def reverse(x: int) -> int:
    # Handle sign
    sign = 1 if x >= 0 else -1
    x = abs(x)

    # Reverse digits
    reversed_num = 0
    while x > 0:
        digit = x % 10
        reversed_num = reversed_num * 10 + digit
        x //= 10

    # Check 32-bit bounds
    if reversed_num > 2**31 - 1 or reversed_num < -2**31:
        return 0

    # Apply sign
    return sign * reversed_num

Complexity

  • Time Complexity: O(log x) – Number of digits is logarithmic in x.
  • Space Complexity: O(1) – Uses only a few variables.

Efficiency Notes

This is fast and simple, avoiding string conversion, and handles overflow directly. It’s the standard solution for this problem.

Alternative: String Conversion (Brief Mention)

Explanation

You could convert the integer to a string, reverse it (e.g., "123" to "321"), then convert back to an integer and check bounds. It’s easier to code but slower due to string operations and less preferred in interviews, so we focus on the math approach.

Additional Example

For x = 1534236469:

  • Goal: Reverse to 9646324351.
  • Steps:
    • Sign +1, work with 1534236469.
    • Digits: 9, 6, 4, 6, 3, 2, 3, 4, 5, 1.
    • Build: 9, 96, 964, ..., 9646324351.
  • Overflow: 9646324351 > 2,147,483,647.
  • Result: Return 0, as it exceeds 32-bit bounds.

Edge Cases

  • Zero: x = 0 – Returns 0.
  • Overflow: x = 1534236469 – Returns 0.
  • Negative: x = -120 – Returns -21.
  • Max/Min Bounds: x = 2³¹ - 1 – Checks properly.

Final Thoughts

  • Mathematical Approach: Efficient and elegant, great for learning digit manipulation.
  • Practice Value: Teaches handling numbers and overflow, useful for similar problems.