### Problem

We need to check whether a provided number `num`

is a *Palindrome*. A Palindrome number is a number that reads the same forward and backward. This puzzle does not allow the conversion of the number to a string or the use of other auxiliary data structures.

#### Examples:

Input `num` | Output |

`212` | `true` |

`112211` | `true` |

`1` | `true` |

`123` | `false` |

`10` | `false` |

`-121` | `false` |

### Solution

```
fn is_palindrome(mut num: i32) -> bool {
match num {
n if n == 0 => return true, //0 is palindrome
n if n < 0 => return false, //negative num is not
n if n % 10 == 0 => return false, //num ending 0 is not
_ => (),
}
//reversing the half of the num (reversing the whole number could
//cause int overflow):
let mut num_reversed = 0;
while num > num_reversed {
num_reversed = num_reversed * 10 + num % 10;
num /= 10;
}
//if num originally had an even number of digits e.g. 1221 then
//[num == num_reversed == 12].
//if num had an odd number of digits e.g. 12321 then
//[num == 12, num_reversed = 123], the mid number (3)
//could be ignored in this case.
num == num_reversed || num == num_reversed / 10
}
```

### Explanation

The first idea that would usually come to mind about this puzzle is to convert the number to a string and then work with the string to see if it is a palindrome or not. But the conversion is not allowed by the puzzle requirement.

Conceptually, we could *decompose* the `num`

by applying the division and modulo operations. At the same time, we could *compose* the *reversed* number `num_reversed`

. If the `num`

is equal to the `num_reversed`

, then it is a palindrome. One setback with this approach is that, in theory, we could overflow `i32`

when reversing some ridiculously large value like `i32::MAX`

. To get around that, we could reverse only half of the number - and it still would be enough to determine if the number is a palindrome or not.

Let's consider the process for the input `num = 1221`

:

On the first iteration,

`num_reversed = num_reversed * 10 + num % 10 = 0 * 10 + 1221 % 10 = 1`

. That is the last digit of`1221`

. Then we update`num = num / 10 = 1221 / 10 = 122`

.On the second iteration,

`num_reversed = num_reversed * 10 + num % 10 = 1 * 10 + 122 % 10 = 12`

. That is the reversed last 2 digits of`1221`

. Then we update`num = num / 10 = 122 / 10 = 12`

. That is the end of the`while`

loop.The function returns

`true`

because`num == num_reversed == 12`

.

In the case of a number with an odd number of digits e.g. `12321`

, the last step would require an additional division of the `num_reversed`

by `10`

because we would have `num == 12`

and `num_reversed = 123`

. The division would help us to eliminate that last digit `3`

from the comparison - which is safe because the middle digit (`3`

is the middle digit of `12321`

number) is irrelevant to our process anyway.

### Complexity

The time complexity of this solution is `O(log n)`

(`n`

is the input number `num`

). The auxiliary space complexity is `O(1)`

.