The Reverse Integer problem on LeetCode is a coding challenge that asks you to reverse the digits of a given 32-bit integer and return the reversed integer. If the reversed integer is out of the range of 32-bit integers, you should return 0.

For a signed 32-bit integer, the min value is $-2^{31}$, which is equal to $-2147483648$. The max value is $2^{31} - 1$, which is equal to $2147483647$. This is because the most significant bit (the leftmost bit) is used to indicate the sign of the number, leaving 31 bits to store the magnitude.

For example, if the input is $123$, the output should be $321$. If the input is $-120$, the output should be $-21$. If the input is $1534236469$, the output should be $0$ because the reversed integer is $9646324351$, which is larger than $2^{31} - 1$.

```
#include <cassert>
#include <climits> // INT_MAX, INT_MIN
#include <iostream>
using namespace std;
int reverse(int x) {
int reversed = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (reversed > INT_MAX / 10 || (reversed == INT_MAX / 10 && pop > 7)) {
return 0;
}
if (reversed < INT_MIN / 10 || (reversed == INT_MIN / 10 && pop < -8)) {
return 0;
}
reversed = reversed * 10 + pop;
}
return reversed;
}
int main() {
assert(reverse(12345) == 54321);
assert(reverse(-54321) == -12345);
assert(reverse(1534236469) == 0); // overflow
cout << "All test cases passed!" << endl;
return 0;
}
```

The step of checking overflow is to prevent the result from exceeding the range of a signed 32-bit integer, which is $[-2^{31}, 2^{31} - 1]$. This means that the result cannot be less than $-2^{31}$ or greater than $2^{31} - 1$. If the result goes beyond this range, the function should return $0$.

- If the result is greater than
`INT_MAX / 10`

, then adding any digit will cause overflow. - If the result is equal to
`INT_MAX / 10`

, then adding a digit greater than 7 will cause overflow. - If the result is less than
`INT_MIN / 10`

, then adding any digit will cause underflow. - If the result is equal to
`INT_MIN / 10`

, then adding a digit less than -8 will cause underflow.

Performing the overflow check within the loop ensures that the final result stays within the valid integer range. It prevents unexpected behavior or errors that might occur if overflow wasnβt handled until after the loop.

```
import Foundation
func reverse(_ x: Int) -> Int {
var original: Int = x
var reversed: Int = 0
while original != 0 {
let digit = original % 10
original = original / 10
// Check overflow against Int32.max which is 2147483647
if (reversed > Int32.max / 10) || (reversed == Int32.max / 10 && digit > 7) {
return 0
}
// Check overflow againts Int32.min which is -2147483648
if (reversed < Int32.min / 10) || (reversed == Int32.min / 10 && digit < -8) {
return 0
}
reversed = reversed * 10 + digit
}
return reversed
}
// Test cases
assert(reverse(123) == 321)
assert(reverse(-123) == -321)
assert(reverse(120) == 21)
assert(reverse(1534236469) == 0) // Exceeds 32-bit signed integer range
assert(reverse(-2147483648) == 0) // Exceeds 32-bit signed integer range
assert(reverse(7) == 7)
assert(reverse(0) == 0)
assert(reverse(-8) == -8)
print("All test cases passed!")
```

Polynomial Rolling HashJun 06, 2024

Big-O NotationFeb 06, 2024

RabinβKarp String SearchingSep 10, 2021

Dynamic Programming (DP)Jan 16, 2022

Competitive Programming TopicsFeb 02, 2022

Bloom FilterFeb 02, 2022

Data Structures Used in Competitive ProgrammingFeb 04, 2022