LeetCode 7 solution

Problem Statement (LeetCode 7 - Reverse Integer)

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

Function Signature

int reverse(int x);

---

Example Input & Output

Example 1

Input: x = 123
Output: 321

Example 2

Input: x = -123
Output: -321

Example 3

Input: x = 120
Output: 21

Example 4 (Overflow Case)

Input: x = 1534236469
Output: 0

(Since reversing it would exceed 2³¹ - 1 = 2147483647, return 0).

---

Optimal Approach: Digit Extraction & Overflow Check (O(log n) Solution)

Intuition

1. Extract digits one-by-one from x using mod 10 (x % 10).
2. Build the reversed number using rev = rev * 10 + last_digit.
3. Check for 32-bit integer overflow before updating rev:
   • If rev > INT_MAX / 10 or rev == INT_MAX / 10 and last_digit > 7 → Overflow.
   • If rev < INT_MIN / 10 or rev == INT_MIN / 10 and last_digit < -8 → Overflow.

Time & Space Complexity

• Time Complexity: O(log n) (We process each digit, and x has at most log₁₀(x) digits).
• Space Complexity: O(1) (We use only a few integer variables).

---

LeetCode-Compatible C++ Code

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int digit = x % 10;
            x /= 10;
            
            // Overflow check before updating rev
            if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && digit > 7)) return 0;
            if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && digit < -8)) return 0;

            rev = rev * 10 + digit;
        }
        return rev;
    }
};

---

Step-by-Step Explanation

Example 1: x = 123

Step 1: Extract digit → 3, rev = 0 * 10 + 3 = 3
Step 2: Extract digit → 2, rev = 3 * 10 + 2 = 32
Step 3: Extract digit → 1, rev = 32 * 10 + 1 = 321

Final Output: 321 ✅

---

Example 2: x = -123

Step 1: Extract digit → -3, rev = 0 * 10 + (-3) = -3
Step 2: Extract digit → -2, rev = -3 * 10 + (-2) = -32
Step 3: Extract digit → -1, rev = -32 * 10 + (-1) = -321

Final Output: -321 ✅

---

Example 3: x = 120

Step 1: Extract digit → 0, rev = 0 * 10 + 0 = 0
Step 2: Extract digit → 2, rev = 0 * 10 + 2 = 2
Step 3: Extract digit → 1, rev = 2 * 10 + 1 = 21

Final Output: 21 ✅

---

Example 4: Overflow Check (x = 1534236469)

Step 1-8: Reverse partially → rev = 964632435
Step 9: Extract digit = 1
  rev = 964632435 * 10 + 1 = 9646324350 (Exceeds INT_MAX)
  → Return 0

Final Output: 0 (overflow detected) ✅

---

Alternative Approaches & Why Not?

1️⃣ Using String Manipulation

• Convert x to a string, reverse it, and convert back to an integer.
• ❌ Extra Space: Uses O(n) space.
• ❌ Handling negative sign requires additional conditions.
• ❌ Slower Execution due to extra conversions.
• ✅ Easier to implement, but inefficient.

2️⃣ Stack-Based Approach

• Push digits into a stack, then pop to reverse.
• ❌ Extra Space: Uses O(n) stack space.
• ❌ Slower execution due to stack operations.

3️⃣ Mathematical Approach Without Using rev

• Use bitwise operations to reverse the number in-place.
• ✅ Works but hard to understand & maintain.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Digit Extraction (Best)	O(log n)	O(1)	Simple & efficient
String Manipulation	O(n)	O(n)	Uses extra space
Stack-Based Approach	O(n)	O(n)	Memory-intensive
Bitwise Manipulation	O(log n)	O(1)	Hard to maintain

---

Conclusion

• The digit extraction approach is the most efficient & optimal.
• Brute force methods (String, Stack) are inefficient due to extra space and operations.
• Time Complexity: O(log n)
• Space Complexity: O(1)

---

Recommended Problems for Practice

1. Palindrome Number 🧩
2. Integer to Roman 🔢
3. String to Integer (atoi) 📖

---

Master Integer Manipulation & Overflow Handling! 🚀