## 7 – Reverse Integer

### Problem statement

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: [−231, 231 − 1].

For the purpose of this problem, assume that your function returns

0 when the reversed integer overflows.

Taken from:

leetcode

### Approach and Analysis

#### Flipping via modulo and division

I found the best way to approach this problem was in terms of

how to get the first digit. We can do that by taking mod 10

of the number:

`123 % 10 = 3`

Subsequent digits can be obtained by dividing by 10 and repeating

this process:

123 % 10 = 3 <- 123 / 10 = 12 12 % 10 = 2 <- 12 / 10 = 1 1 % 10 = 1 <-

Now, we can wrap that all in a loop, here’s the pseudocode:

ans = 0; while(num > 0): ans = num % 10 + (ans * 10) num = num / 10

**Note**: We multiply our answer by 10 each time to effectively

“shift” it up to the next 10’s position.

This pseudocode is on the way to a good solution but there are

a couple pieces missing still.

For one, this won’t work if num is less than 0 (because the while

loop won’t go through any iterations). This can be easily be solved

by changing to condition in the loop to `while(num != 0)`

Secondly, the problem states that we can only store integers in the

32-big signed integer range and that we should return 0 when the

reverse integer overflows. This is a huge clue that we will have to

handle this scenario.

### Aside – Integer Overflow

Integer overflow in this problem can occur when we try and reverse

a number that is too big for the data type it’s being stored in.

For example, imagine for the sake of simplicity that this problem

involved 4 bits instead of 32 (for simplicity) and that the number

we wanted to reverse was 14. This could be represented in binary as

`0b1110`

. We would expect that reversing 14 would return 41 but this

is in fact impossible because we cannot represent the number 41 with

only 4 bits (this highest is 15!).

If we don’t check our code for overflow, we are likely to get

unexpected results when provided with extremely large values.

### Rust solution (clumsy)

impl Solution { pub fn reverse(x: i32) -> i32 { let isPositive = x > 0; let mut accumulator: i32 = 0; let mut mutx = (x.abs()); while (mutx >= 1) { let digit: i32 = mutx % 10; // use checked_mul to avoid overflow, evaluates the // `None` arm if overflow is found match accumulator.checked_mul(10) { None => return 0, Some(fine) => { accumulator = accumulator * 10; } } match accumulator.checked_add(digit) { None => return 0, Some(fine) => { accumulator = accumulator + digit; } } mutx = mutx / 10; } if (isPositive) { return accumulator; } else { return -accumulator; } } }

This solution passes all the test cases that leetcode provides but

it has some quirks that we can easily avoid.

Firstly, we can remove additional logic to deal with the negative

case, namely lines 3 and 23 through 27 simply by making the fix to

our `while`

loop as suggested in the previous section.

Secondly, the match statements can be chained together such that the

entire `checked_add`

function is contained in the “success” arm of

the `checked_mul`

function:

impl Solution { pub fn reverse(x: i32) -> i32 { let mut accumulator: i32 = 0; let mut mutx = x; while (mutx != 0) { let digit: i32 = mutx % 10; match accumulator.checked_mul(10) { None => return 0, // By this point, tmp will contain the result of // evaluating `checked_mul(10)` on accumulator Some(tmp) => { match tmp.checked_add(digit) { None => return 0, Some(fine) => { accumulator = fine; } } } } mutx = mutx / 10; } return accumulator; } }

Note that in either solution, the first thing we have to do is

create mutable variables both of the input and output. By default,

the rust compiler won’t mutate x and that’s a very good thing.

### What I learned by solving this problem

#### Thinking about the negative case

My first approach to tackling the negative case was not very elegant;

instead of looking at how to modify the solution to fit the case, I

thought about how to modify the case to fit the solution (taking the

absolute value and then “re-reversing” it). This pattern should serve

as a warning to me in the future that there is probably a better way

to accomplish this.

#### Checked functions

Clearly although Rust is a lot more stringent than other languages,

problems like these can still sideline you if you’re not careful.

Rust’s default add and multiply operations don’t handle overflow

(and justifiably so – one might want to handle it their own way)

and that simply means we need to reach deeper into our toolbox for

the right tool to deal with that job. Checked functions are a useful

tool in that regard, and they seem to work great!

#### Getting used to “match”

Match is a little foreign to a Rust newbie like myself but his problem

provided some decent experience working with it. An important lesson

I learned was that the `Some`

arm stores the *evaluation* of the

statement in question so there’s no need for intermediate “mumbo jumbo”.