LeetCode Solution: 7. Reverse Integer

#leetcode #dsa #programming #tutorial

Brain Teaser: Can You Reverse an Integer Without Breaking the Bank? (LeetCode #7)

Hey there, fellow coding adventurers! 👋 Vansh2710 here, ready to dive into another classic LeetCode challenge. Today, we're tackling problem #7: Reverse Integer. It sounds super simple, right? Just flip the digits! But as with many LeetCode problems, there's a sneaky little twist that makes it a fantastic learning experience about handling real-world integer limits.

Let's unravel this puzzle together!

📚 Problem Explanation: The Core Challenge

Imagine you have a number, say 123. Your task is to reverse its digits to get 321. Sounds simple, right? What about negative numbers? If x = -123, the output should be -321. And if x = 120, the reversed number is 21 (we naturally drop leading zeros, so 021 becomes 21).

Here's the catch: We're dealing with a "signed 32-bit integer". This means our numbers have a strict upper and lower limit: they can go from (-2^31) to (2^31 - 1). That's roughly from -2 billion to +2 billion. If reversing the number causes it to go beyond these limits (an "overflow"), your function must return 0.

And another critical rule: You cannot use 64-bit integers (like long long in C++) to store your result temporarily. This forces us to be clever with our overflow checks!

Examples:

Input: x = 123 Output: 321
Input: x = -123 Output: -321
Input: x = 120 Output: 21

🧠 Intuition: How Do We "Flip" Numbers Digit by Digit?

Let's break down the mechanics of reversing a number. How would you do it manually, one digit at a time?

Getting the Last Digit: To grab the last digit of any integer, we can use the modulo operator (% 10).
- For 123, 123 % 10 gives 3.
- For 12, 12 % 10 gives 2.
- For 1, 1 % 10 gives 1.
Removing the Last Digit: After we've extracted a digit, we need to chop it off the original number. We can do this with integer division (/ 10).
- For 123, 123 / 10 gives 12.
- For 12, 12 / 10 gives 1.
- For 1, 1 / 10 gives 0.
Building the Reversed Number: We need a variable to store our reversed number, let's call it reversed_num, initialized to 0. Each time we extract a digit, we'll "shift" our current reversed_num one place to the left (by multiplying by 10) and then add the new digit.

Let's trace x = 123:
- Start: x = 123, reversed_num = 0
- Iteration 1:
  - digit = 123 % 10 = 3
  - reversed_num = 0 * 10 + 3 = 3
  - x = 123 / 10 = 12
- Iteration 2:
  - digit = 12 % 10 = 2
  - reversed_num = 3 * 10 + 2 = 32
  - x = 12 / 10 = 1
- Iteration 3:
  - digit = 1 % 10 = 1
  - reversed_num = 32 * 10 + 1 = 321
  - x = 1 / 10 = 0
- Loop ends because x is now 0. Return 321. Perfect!

The "aha!" moment is realizing this iterative process. The BIGGEST "aha!" (and the trickiest part) is figuring out how to check for overflow before it actually happens, because once an integer overflows, its value becomes unpredictable!

🛠️ Approach: The Step-by-Step Logic

Combining our intuition, here's the detailed plan to solve the Reverse Integer problem, keeping the overflow constraint in mind:

Initialize num = 0: This variable will store our result as we build it digit by digit. We're using num as per the provided solution snippet's variable name.
Loop While x is Not Zero: We'll keep extracting digits from x and adding them to num until x becomes 0.
The Critical Overflow Check: This is the most vital part! Before we update num (by multiplying by 10 and adding a new digit), we need to check if this operation will cause num to exceed the INT_MAX (maximum 32-bit integer) or fall below INT_MIN (minimum 32-bit integer).

The specific check provided in the solution snippet is:
if (num > INT_MAX / 10 || num < INT_MIN / 10)

Let's break down why this works:
- INT_MAX is the largest positive 32-bit integer (typically 2,147,483,647).
- INT_MIN is the smallest negative 32-bit integer (typically -2,147,483,648).
- If num is already greater than INT_MAX / 10, then multiplying num by 10 (even before adding the digit) will definitely exceed INT_MAX. For example, if INT_MAX / 10 is roughly 2.1e8, and num is 3e8, then 3e8 * 10 = 3e9 is clearly too big.
- The same logic applies to INT_MIN / 10 for checking negative overflow.
- If this condition is true, we immediately return 0 because an overflow is imminent.
Extract the Last Digit: int digit = x % 10; (e.g., if x=123, digit=3). This digit will be appended to num.
Build the Reversed Number: num = num * 10 + digit;
- This shifts the existing digits in num one position to the left and adds the newly extracted digit to the rightmost position.
Remove the Last Digit from x: x = x / 10;
- This prepares x for the next iteration, effectively "eating away" its digits from right to left.
Return num: Once the while loop finishes (meaning x has become 0 and all digits have been processed), num will hold the correctly reversed integer. If any overflow was detected, we would have returned 0 earlier.

💻 Code: Bringing It All Together (C++)

Here's the C++ implementation following our approach. Note that INT_MAX and INT_MIN are defined in the <limits.h> (or <climits>) header.

#include <limits.h> // Required for INT_MAX and INT_MIN

class Solution {
public:
    int reverse(int x) {
        int num = 0; // This variable will store our reversed number

        // Loop as long as there are digits left in x
        while (x != 0) {
            // --- OVERFLOW CHECK ---
            // This is the critical step. We check for potential overflow *before*
            // we perform the multiplication and addition that could cause it.
            // If 'num' is already so large (or small) that multiplying by 10
            // would exceed INT_MAX (or INT_MIN) even before adding the last digit,
            // we know an overflow is inevitable.
            if (num > INT_MAX / 10 || num < INT_MIN / 10) {
                return 0; // Overflow detected, return 0 as per problem statement
            }
            // --- END OVERFLOW CHECK ---

            // Extract the last digit of x
            int digit = x % 10;

            // Build the reversed number:
            // 1. Multiply 'num' by 10 to shift its existing digits one position to the left.
            // 2. Add the newly extracted 'digit' to the rightmost position.
            num = num * 10 + digit;

            // Remove the last digit from x to process the next digit in the next iteration
            x = x / 10;
        }

        // After the loop, 'num' holds the completely reversed integer
        return num;
    }
};

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log |x|)
- The while loop runs once for each digit in the input number x.
- The number of digits in an integer x is proportional to log10(|x|). For example, log10(100) is 2, meaning 3 digits.
- Therefore, the time complexity is logarithmic with respect to the absolute value of x.
Space Complexity: O(1)
- We are only using a few constant-space variables (num, digit, x).
- The memory usage does not grow with the size of the input number.

🌟 Key Takeaways

Digit Manipulation is Key: The modulo % 10 and integer division / 10 operators are your best friends for breaking down and building numbers digit by digit.
Edge Cases are Crucial: Always consider negative inputs and numbers ending in zero (like 120).
The Overflow Challenge: When working with fixed-size integer types, understanding and implementing pre-emptive overflow checks is paramount. Doing the check before the potentially overflowing operation is the way to go, especially when you can't use larger data types.
Practice Makes Perfect: These types of problems build a strong foundation for thinking about integer properties and constraints.

Happy coding, and see you in the next LeetCode adventure! ✨

Author Account: Vansh2710
Time Published: 2026-04-24 00:43:37

DEV Community