# Solution by vitaly_bilanchuk

• ### 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).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.