### Question

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 hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

### Solution

#### Approach #1 Reordering

**Intuition**

Reverse number by changing digits order.

**Algorithm**

Assume that integer number **X** is a view of an array of digits **d1, d2, ... dN**. In these case the following formula is applied:

**X** = ( ... ((**d[1]** * 10 + **d[2]**) * 10 + **d[3]** ) * 10 ... ) * 10 + **d[N]**; {1}

For example:

487 = (4 * 10 + 8) * 10 + 7 = (40 + 8) * 10 + 7 = 48 * 10 + 7= 480 + 7 = 487

The main idea is in reversing **d[...]** array. In this case reverted array is **dN, dN-1, ... d2, d1**

and reverted integer number **RX** could be found by the following formula:

**RX** = ( ... ((**d[N]** * 10 + **d[N-1]**) * 10 + **d[N-2]** ) * 10 ... ) * 10 + **d[1]**; {2}

or (after hiding brackets according the mathematical rules)

**RX** = **d[N]** * 10^(N-1) + **d[N-1]** * 10^(N-2) + .. + **d[1]** * 10^0; {3}

It is seen that we should go one by element ( digit ) and calculate **RX** by the previous formula {2} or {3}.

A one of the good ways (easy way) of doing this is cutting elements ( digits ) from **X** using the remainder of division:

The algorithm ( with an example of cutting 487 number) is the following:

- Define the first element and its new position. An element is equal the reminder of division by 10. It is 7 for 487.
- The position equals size of all elements in a number. Take X/10 number ( 48 in our case ) and apply the previous operation to define the next element ( digit ). Repeat it recursively and define a size for all digits and their values.
- Make calculation of the current
**RX**value using digit and its position - All digits should be involved.

The algorithm uses recursion and has the check for overflows.

The main idea is checking added element at the begin ( left ) of **RX**.

**C++**

```
// function for getting @dpos digit of number @x.
int getDigit(int x, size_t dpos)
{
return ( x / (int) pow(10, dpos - 1) ) % 10;
}
// an iteration function. It is used to find digits and define their positions in reserved number
int reverseIteration(int x, size_t& size)
{
if(x / 10 == 0)
{
size = 1;
return x;
}
// define the last digit
int digit = x%10;
// define cut number
int reversedSubX = reverseIteration(x/10, size);
// add the digit to reversed number
int reversedX = digit * pow(10,size) + reversedSubX;
size++;
// check overflows
if(getDigit(reversedX, size) != digit)
{
return 0;
}
return reversedX;
}
int reverse(int x)
{
size_t size; // number size. temporal
return reverseIteration(x, size);
}
```

*Negative number:* in the case of a negative number all digits and reversedSubX values are negative too.

**Complexity Analysis**

- Time complexity : $$O(n)$$ ( or $$O(1)$$ in the current case)

We need to iterate over all elements in a number. But the task says about integer number ( n <= 10 ). So it is not too complex.

- Space complexity : $$O(n)$$.

We need $$O(n)$$ space for storing intermediate values ( digits, reversedX, reversedSubX).