Reverse Integer
LeetCode #7 · Medium · Math · C++ solution with worked-out approach and complexity analysis.
Approach
Build Reversed Number with Overflow Check
Key insight
Before multiplying by 10, check if the result would overflow. If res > INT_MAX/10, multiplying by 10 will overflow. If res < INT_MIN/10, multiplying by 10 will underflow.
Time
O(log x)
number of digits
Space
O(1)
Problem description(from LeetCode)
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).
Examples
Example 1
- Input:
- x = 123
- Output:
- 321
Constraints
- •-2^31 <= x <= 2^31 - 1
C++ Solution
solution.cpp
class Solution {
public:
int reverse(int x) {
int res = 0;
while (x) {
if (res > (INT_MAX / 10) || res < (INT_MIN / 10)) return 0;
res = res * 10 + (x % 10);
x /= 10;
}
return res;
}
};