Description
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 [-231, 231 - 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:
-231 <= x <= 231 - 1
Solutions
Solution 1: Mathematics
Let's denote mi and mx as -2^{31} and 2^{31} - 1 respectively, then the reverse result of x, ans, needs to satisfy mi \le ans \le mx.
We can continuously take the remainder of x to get the last digit y of x, and add y to the end of ans. Before adding y, we need to check if ans overflows. That is, check whether ans × 10 + y is within the range [mi, mx].
If x \gt 0, it needs to satisfy ans × 10 + y ≤ mx, that is, ans × 10 + y ≤ \left \lfloor mx⁄10 \right \rfloor × 10 + 7. Rearranging gives (ans - \left \lfloor mx⁄10 \right \rfloor) × 10 ≤ 7 - y.
Next, we discuss the conditions for the inequality to hold:
- When ans \lt \left \lfloor mx⁄10 \right \rfloor, the inequality obviously holds;
- When ans = \left \lfloor mx⁄10 \right \rfloor, the necessary and sufficient condition for the inequality to hold is y ≤ 7. If ans = \left \lfloor mx⁄10 \right \rfloor and we can still add numbers, it means that the number is at the highest digit, that is, y must not exceed 2, therefore, the inequality must hold;
- When ans \gt \left \lfloor mx⁄10 \right \rfloor, the inequality obviously does not hold.
In summary, when x \gt 0, the necessary and sufficient condition for the inequality to hold is ans ≤ \left \lfloor mx⁄10 \right \rfloor.
Similarly, when x \lt 0, the necessary and sufficient condition for the inequality to hold is ans ≥ \left \lfloor mi⁄10 \right \rfloor.
Therefore, we can check whether ans overflows by checking whether ans is within the range [\left \lfloor mi⁄10 \right \rfloor, \left \lfloor mx⁄10 \right \rfloor]. If it overflows, return 0. Otherwise, add y to the end of ans, and then remove the last digit of x, that is, x \gets \left \lfloor x⁄10 \right \rfloor.
The time complexity is O(log |x|), where |x| is the absolute value of x. The space complexity is O(1).
class Solution: def reverse(self, x: int) -> int: ans = 0 mi, mx = -(2**31), 2**31 - 1 while x: if ans < mi // 10 + 1 or ans > mx // 10: return 0 y = x % 10 if x < 0 and y > 0: y -= 10 ans = ans * 10 + y x = (x - y) // 10 return ans(code-box)
