Rust Interview Puzzles: Check if a number is Palindrome

·

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)`.

Rust Playground with this code