grid47 Exploring patterns and algorithms
Nov 6, 2024
4 min read
Solution to LeetCode 7: Reverse Integer Problem
Reverse the digits of a signed 32-bit integer. If the reversed integer is outside the range of a signed 32-bit integer, return 0. You are restricted from using 64-bit integers.
Problem
Approach
Steps
Complexity
Input: The input is a signed 32-bit integer.
Example: Input: x = 456
Constraints:
• -2^31 <= x <= 2^31 - 1
Output: The output is the reversed integer or 0 if the reversed integer exceeds the 32-bit signed integer range.
Example: Output: 654
Constraints:
• If reversing causes overflow, return 0.
Goal: Reverse the digits of the input integer while ensuring the result does not exceed the 32-bit integer range.
Steps:
• Extract digits one by one using modulus and division.
• Check for potential overflow before appending the digit to the result.
• Stop and return 0 if the next step would exceed the integer limits.
• Return the reversed number.
Goal: The solution must operate within the bounds of a 32-bit integer.
Steps:
• -2^31 <= x <= 2^31 - 1
• No 64-bit integer storage allowed.
Assumptions:
• Input integer will always be within the 32-bit signed range.
• Negative numbers retain their sign after reversal.
• Input: Input: x = 456
• Explanation: Reverse the digits of 456 to get 654.
• Input: Input: x = -890
• Explanation: Reverse the digits of -890 to get -98.
• Input: Input: x = 0
• Explanation: The reversed digits of 0 is still 0.
Approach: Simulate the digit reversal process and manage overflow using checks before appending each digit.
Observations:
• Reversing the digits is straightforward using modulus and division.
• Overflow must be checked at each step before modifying the result.
• Use conditions to handle cases where the next digit causes overflow or underflow.
Steps:
• Initialize an integer to store the reversed number.
• Iteratively extract the last digit from the input number using modulus.
• Check if adding this digit to the reversed number would cause overflow.
• Append the digit to the reversed number.
• Continue until all digits are processed.
• Return 0 if an overflow condition is met; otherwise, return the reversed number.
Empty Inputs:
• Not applicable as input is always provided.
Large Inputs:
• Test with inputs close to the integer boundaries like -2147483648 and 2147483647.
Special Values:
• Test with 0 and single-digit numbers.
Constraints:
• Ensure that overflow cases return 0 as expected.
intreverse(int x)
{
int rev=0, pop;
while(x !=0)
{
pop = x %10;
x /=10;
if( (rev > INT_MAX/10|| (rev == INT_MAX/10&& pop >7)) || (rev < INT_MIN/10|| (rev == INT_MIN/10&& pop <-8)) )
return0;
rev = rev *10+ pop;
}
return rev;
}
1 : Function Declaration
int reverse(int x)
Declare the `reverse` function, which takes an integer `x` as input and returns the reversed integer.
2 : Variable Initialization
int rev=0, pop;
Initialize variables `rev` and `pop` to store the reversed integer and the popped digit, respectively.
3 : Loop Iteration
while(x !=0)
Start a loop that continues as long as `x` is not zero.
4 : Modulo Operation
pop = x %10;
Extract the last digit of `x` using the modulo operator and store it in `pop`.
5 : Integer Division
x /=10;
Remove the last digit from `x` by integer division.
6 : Conditional Check
if( (rev > INT_MAX/10|| (rev == INT_MAX/10&& pop >7)) ||
Check if the reversed integer `rev` is about to exceed the maximum integer value.
7 : Conditional Check
(rev < INT_MIN/10|| (rev == INT_MIN/10&& pop <-8)) )
Check if the reversed integer `rev` is about to go below the minimum integer value.
8 : Return Value
return0;
If overflow or underflow occurs, return 0.
9 : Mathematical Operations
rev = rev *10+ pop;
Multiply `rev` by 10 and add the popped digit `pop` to it.
10 : Return Value
return rev;
Return the reversed integer `rev`.
Best Case: O(d)
Average Case: O(d)
Worst Case: O(d)
Description: Where 'd' is the number of digits in the integer, as each digit is processed once.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses constant space for variables.
