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:

1. the sign
2. the number at each bit in decimal base
3. 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: whether r overflows is unknown.

Then it's clear this is an automata with memory:

• If state[i] == 0, then state[i+1] == 0;
• If state[i] == 1, then state[i+1] == 1;
• If state[i] == 2, then
  • If r[i+1] < b[i+1], then state[i+1] == 0;
  • If r[i+1] > b[i+1], then state[i+1] == 1;
  • If r[i+1] == b[i+1], then state[i+1] == 2;

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;}
    }
}