## 9 – Palindrome Number

### Problem statement

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

**Example 1**:

Input: 121 Output: true

**Example 2**:

Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

**Example 3**:

Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Could you solve it without converting the integer to a string?

Taken from:

leetcode

### Approach and Analysis

#### Approach #1

I found the most intuitive approach to this problem was to create arrays

consisting of each digit in the integer, both in ascending and descending

order. Then they could be compared, and if found to be the same, the

integer is a palindrome.

In order to create the inverted array, we can use the same procedure as with

reverse integer of progressively taking the last digit using modulus 10

(% 10) and dividing by 10 until we reach 0.

#### Approach #2

This solution is like #1 except that instead of creating arrays,

we can simply accumulate on a number. In this case, we need only

generate the inverted number using our progressive modulus procedure,

which we can then compare to the input number.

One issue with this approach is that our inverted integer may overflow

(see reverse integer post for a discussion about this). To solve this

problem, we can invert the latter half of the integer and compare it to

the first half of the original (recall, they should match if they are

truly palindromes).

#### Complexity

The complexities for either approach is as follows:

- O(log
_{10}(n)) time complexity - We have to iterate through the base 10 order of magnitude

of the input number. - O(1) space complexity
- This should be intuitive: this algorithm takes no more space than

it does to store an integer or array that is the max length of an

integer, which doesn’t vary based on input size.

### Rust solution (Approach #1)

impl Solution { pub fn is_palindrome(x: i32) -> bool { if (x < 0) { return false; } let mut stack = vec![]; let mut mutx: i32 = x; while (mutx != 0) { stack.push(mutx % 10); mutx /= 10; } let mut reversed_stack = stack.clone(); reversed_stack.reverse(); for (index, element) in stack.iter().enumerate() { if (*element != reversed_stack[index]) { return false; } } return true; } }

I see the biggest issue with this solution being:

- Use of high-level vector methods. This means:
- The solution is less portable to other languages
- Implementing it requires knowledge of vector methods

### Rust solution (Approach #2)

impl Solution { pub fn is_palindrome(x: i32) -> bool { let mut mutx = x; # We need to check the case where x ends with a 0 but # doesn't start with 0 (ie. isn't 0). If we don't, # in the case where x is 10, both revertedNumber and mutx # will be 1, which will return true if (mutx < 0 || (mutx % 10 == 0) && (mutx != 0)) { return false; } let mut revertedNumber: i32 = 0; while (mutx > revertedNumber) { revertedNumber = revertedNumber * 10 + mutx % 10; mutx /= 10; } # In the case where a digit is odd, mutx will be longer than # the reverted number ex. when x = 12321, mutx = 12 and # revertedNumber = 123. We can divide the mutated number # by 10 to solve this problem return (mutx == revertedNumber) | (mutx == revertedNumber / 10); } }

The problem with this solution is that we have to deal with edge cases

such as when end of the number is 0 and when the number is odd.

### Bonus solution (Approach #1)

I posted my solution to this problem using approach #1 in a discussion

post on leetcode and a very kind individual named

ObliqueMotion provided

excellent feedback that I’ll outline below:

impl Solution { # Change the function sinature to avoid redeclaring x as a mut pub fn is_palindrome(mut x: i32) -> bool { # There should be no parentheses around the condition in the # `if` statement if x < 0 { return false; } # We may as well allocate only the space we need let mut stack = Vec::with_capacity(10); while x != 0 { stack.push(x % 10); x /= 10; } let half = stack.len() / 2; # This approach is a more idiomatic rust style using iterators stack # Make an interator .iter() # Yield the first `n` elements of the iterator .take(half) # Generate a new iterator with the reversed half and then # `zip` it to the first one .zip(stack.iter().rev().take(half)) # Takes a closure that returns true or false and applies # it to each element and ensures that they all return `true` .all(|(left_hand_side, right_hand_side)| left_hand_side == right_hand_side) } }

To help explain the iterator section, let’s go through some examples:

Let’s take the following arrays as examples:

`[1, 2, 3, 4]`

– non-palindrome

`[1, 2, 2, 1]`

– palindrome

stack .iter() .take(half)

This will result in an iterator that returns: `[1, 2]`

for both examples

The next line:

.zip(stack.iter().rev().take(half))

will result in an iterator that returns tuples where the 0th element in the tuple is

the first half of the list and the 1st element in the tuple is the reversed second

half of the list (in lockstep), conceptually represented by:

`[(1, 1), (2, 2)]`

– for the palindrome example

`[(1, 3), (2, 4)]`

– for the non-palindrome example

The last line hopefully makes sense considering the explanation given above.

.all(|(left_hand_side, right_hand_side)| left_hand_side == right_hand_side)

### Bonus Solution (Approach #2)

The user who provided feedback on my solution posted his own answer using approach #2 here:

ObliqueMotion’s Solution

### What I learned by solving this problem

Due to the excellent feedback that I received on my solution, I learned a lot about how to

write code in good Rust style.

Of the many things I learned throughout this exercise, getting comfortable with Iterators was probably

the most important one. I feel like this is a great start to “thinking” in a Rust way and to improve

my coding skills in general. You can look forward to seeing many more iterators in future posts!

`.zip`

This method took me the longest to understand but that I feel was well worth the effort. Previously I’ve

always approached this problem by making a for-loop in one of the vectors and then indexing the other one;

an approach that feels antiquated and inelegant compared to using iterators and the `.zip`

method.