Reverse Integer

Mediummath
Category: Bit Manipulation
Companies that ask this question:
AmazonGoogleFacebookBloomberg

Approach

Reverse Integer

Problem Statement

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³¹, 2³¹ - 1], then return 0.

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

Examples

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21
Explanation: Trailing zeros are dropped

Example 4:

Input: x = 1534236469
Output: 0
Explanation: Reversed would be 9646324351, which overflows

Approach

Math-Based Reversal

We reverse the integer digit by digit using modulo and division operations.

Key Steps:

  1. Handle negative numbers by tracking sign
  2. Extract digits one by one: digit = x % 10
  3. Build reversed number: result = result * 10 + digit
  4. Check for overflow before adding each digit
  5. Remove last digit from x: x = x // 10

Overflow Detection:

  • 32-bit signed int range: [-2147483648, 2147483647]
  • Before: result = result * 10 + digit
  • Check: result > MAX // 10 OR result == MAX // 10 and digit > 7
  • Check: result < MIN // 10 OR result == MIN // 10 and digit < -8

Complexity Analysis

  • Time Complexity: O(log x)

    • Number of digits in x is log₁₀(x)
    • We process each digit once

  • Space Complexity: O(1)

    • Only use a constant amount of extra space

Edge Cases

  1. Zero: Return 0
  2. Single digit: Return as is
  3. Negative numbers: Preserve sign
  4. Trailing zeros: Automatically dropped (120 → 21)
  5. Overflow: Return 0 if result exceeds 32-bit range
  6. Edge of range:
    • 2147483647 → overflow
    • -2147483648 → overflow

Visual Intuition

Example: x = 123

Step 1: digit = 3, result = 0 * 10 + 3 = 3, x = 12
Step 2: digit = 2, result = 3 * 10 + 2 = 32, x = 1
Step 3: digit = 1, result = 32 * 10 + 1 = 321, x = 0

Result: 321

Example: x = -123

Step 1: digit = 3, result = 0 * 10 + 3 = 3, x = -12
Step 2: digit = 2, result = 3 * 10 + 2 = 32, x = -1
Step 3: digit = 1, result = 32 * 10 + 1 = 321, x = 0

Result: -321 (apply negative sign)

Common Mistakes

  1. Not checking overflow: Always check before multiplying by 10
  2. Wrong overflow bounds: Use 2³¹ - 1 = 2147483647, not arbitrary large number
  3. Handling negative incorrectly: In Python, -123 % 10 = 7, not 3
  4. Forgetting trailing zeros: They're automatically dropped

Related Problems

  • Palindrome Number
  • String to Integer (atoi)
  • Integer to Roman

Solution

java
1/**
2 * Reverse Integer
3 * Time: O(log x) - number of digits
4 * Space: O(1)
5 */
6
7class Solution {
8    public int reverse(int x) {
9        int result = 0;
10        
11        while (x != 0) {
12            int digit = x % 10;
13            x /= 10;
14            
15            // Check overflow before multiplying by 10
16            // For positive: result > MAX / 10 or (result == MAX / 10 and digit > 7)
17            // For negative: result < MIN / 10 or (result == MIN / 10 and digit < -8)
18            if (result > Integer.MAX_VALUE / 10 || 
19                (result == Integer.MAX_VALUE / 10 && digit > 7)) {
20                return 0;
21            }
22            if (result < Integer.MIN_VALUE / 10 || 
23                (result == Integer.MIN_VALUE / 10 && digit < -8)) {
24                return 0;
25            }
26            
27            result = result * 10 + digit;
28        }
29        
30        return result;
31    }
32}
33
Loading visualizer...