title: Reverse Integer
tags:
- reverse-integer
- No.7
- simple
- finite-automata
- integer
- overflow
Problem
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^{31}, 2^{31} − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Corner Cases
-2147483648
Solution
Finite Automata Loop Twice
To solve this problem, one must figure out:
- the sign
- the number at each bit in decimal base
- if the reversed integer overflows
For [1]:
We can turn all negative numbers to their opposite, or equivalently take their absolute values. Recover the sign when the result is returned. However, here exists a corner case: x == -2147483648
since the positive number 2147483648
is illegal. In this situation, directly return 0
.
For [2]:
By dividing the positive number by 10
each time, we can gradually get the bits from low to high. It's important to record the length of the number l
and highest factor f
based 10
, l == 4
and f == 1000
for 1234
as an instance.
For [3]:
Instead of comparing numbers in binary base, one can check if the number overflows within decimal base. Here the Finite Automata is used:
Since we only consider the positive case according to [1], we only need to compare the reversed number r
with its upper-bound b = {2, 1, 4, 7, 4, 8, 3, 6, 4, 7}
. If the algorithm runs from i=0
(high) to i=9
(low), we set the state of finite automata at each i
to be state[i]
:
-
state[i] == 0
:r
is a legal positive integer; -
state[i] == 1
:r
overflows; -
state[i] == 2
: whetherr
overflows is unknown.
Then it's clear this is an automata with memory:
- If
state[i] == 0
, thenstate[i+1] == 0
; - If
state[i] == 1
, thenstate[i+1] == 1
; - If
state[i] == 2
, then- If
r[i+1] < b[i+1]
, thenstate[i+1] == 0
; - If
r[i+1] > b[i+1]
, thenstate[i+1] == 1
; - If
r[i+1] == b[i+1]
, thenstate[i+1] == 2
;
- If
The logic looks like:
+---1 +---1
| |
2---+---2---+---2-- ...
| |
+---0 +---0
Note The check of overflow is necessary if and only if l==10
. By intializing state[-1] = 0
, we can skip the check for l < 10
ones.
The total running time is O(2log(x)) <= O(20) with O(20) space complexity. Loop twice is necessary since we need to figure out the length of x
before actual calculation of y
.
class Solution {
public int reverse(int x) {
if (x == -2147483648) {return 0;}
int u = (x < 0) ? (-x) : x;
int l = 1;
int t = 1;
int[] r = new int[10];
// initialize outside the loop to accelerate
// try not to if-else in loop
r[0] = u % 10;
u = u / 10;
while (u > 0) {
r[l] = u % 10;
u = u / 10;
t = t * 10;
l = l + 1;
}
int y = 0;
int state = (l==10) ? 2 : 0;
int[] b = {2, 1, 4, 7, 4, 8, 3, 6, 4, 7};
// O(log(x))
for (int i=0; i<l; i++) {
y = y + r[i] * t;
t = t / 10;
if (state==2) {
if (r[i] < b[i]) {state = 0;}
else if (r[i] > b[i]) {state = 1;}
else {state = 2;}
}
}
if (state==1) {return 0;}
else {return (x < 0) ? -1 * y : y;}
}
}
网友评论