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:

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