Reverse Integer - Complete Solution Guide

Reverse Integer is LeetCode problem 7, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 31 , 2 31 - 1] , then return 0 . Assume the environment does not allow you to store 64-bit integers (signed or unsigned). Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 120 Output: 21 Constraints: -2 31 <= x <= 2 31 - 1

Detailed Explanation

The problem requires reversing the digits of a given 32-bit signed integer. If the reversed integer falls outside the range of [-2³¹, 2³¹ - 1], the function should return 0. A crucial constraint is that we cannot use 64-bit integers to store intermediate results.

Solution Approach

The solution iteratively extracts the last digit of the input number, adds it to the reversed number, and updates both the input and reversed numbers. Before each addition, it checks for potential overflow or underflow conditions based on whether the original number was positive or negative.

Step-by-Step Algorithm

1. Step 1: Determine if the input number `x` is negative. Store this information in a boolean variable `is_negative`.
2. Step 2: Take the absolute value of `x` to work with a positive number for easier digit manipulation. Assign it to `num`.
3. Step 3: Initialize a variable `res` to 0. This variable will store the reversed number.
4. Step 4: Enter a `while` loop that continues as long as `num` is not 0.
5. Step 5: Inside the loop, extract the last digit of `num` using the modulo operator (`pop = num % 10`).
6. Step 6: Remove the last digit from `num` by integer division (`num //= 10` in Python or `num /= 10` in Java/C++).
7. Step 7: Before adding `pop` to `res`, check for potential overflow. If `is_negative` is false (i.e., the original number was positive):
8. - Check if `res > INT_MAX // 10` or `(res == INT_MAX // 10 and pop > INT_MAX % 10)`. If either condition is true, return 0 (overflow).
9. - If `is_negative` is true (i.e., the original number was negative):
10. - Check if `res > ABS_INT_MIN // 10` or `(res == ABS_INT_MIN // 10 and pop > ABS_INT_MIN % 10)`. Where `ABS_INT_MIN` is the absolute value of the minimum integer. If either condition is true, return 0 (underflow).
11. Step 8: Add `pop` to `res` (`res = res * 10 + pop`).
12. Step 9: After the loop finishes, if the original number was negative (`is_negative` is true), return `-res`. Otherwise, return `res`.

Key Insights

• Insight 1: The core operation is extracting digits from the input number using the modulo operator (%) and integer division (// or /) and constructing the reversed number.
• Insight 2: The most challenging aspect is handling potential integer overflow during the reversal process. We need to check if multiplying the intermediate reversed number by 10 and adding the next digit will exceed the 32-bit signed integer range before performing the operation.
• Insight 3: The sign of the input number must be preserved throughout the reversal process and applied correctly to the final reversed number.

Complexity Analysis

Time Complexity: O(log(x))

Space Complexity: O(1)

Topics

This problem involves: Math.

Companies

Asked at: Accenture, Adobe, Amazon, Apple, Bloomberg, Cognizant, Deloitte, EPAM Systems, Infosys, Intel, LTI, Meta, Microsoft, Nvidia, Qualcomm, Samsung, Tech Mahindra, Uber, Wipro, Yahoo, Yandex, tcs.