Rust LeetCode: 9. Palindrome Number

Problem Statment

Given an integer x, return true if x is a palindrome, and* false _otherwise*.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -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: x = 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?

Intuition

The core intuition behind solving the palindrome number problem lies in understanding what a palindrome is: a sequence that reads the same backward as forward. For an integer, this means that if we reverse the digits of the number, it should remain the same as the original number.

Here's the thought process:

• Negative Numbers: Any negative number cannot be a palindrome due to the presence of the minus sign -, which cannot be at the end of a number.
• Reversal and Comparison: If we can reverse the number and it remains unchanged, it's a palindrome.
• Efficiency Considerations: While converting the number to a string and reversing it is straightforward, doing so increases the space complexity. An in-place mathematical reversal could be more efficient.

Approach

Our approach starts by handling the simplest and most intuitive method: converting the number to a string and then comparing the original string with its reversed version. This method is easy to understand and implement but uses extra space for the string conversion.

Imperative Approach Using String Conversion

This approach converts the integer to a string and then uses two pointers to compare characters from both ends of the string, moving towards the center. It's imperative because it uses loops and manual index manipulation. This method is straightforward and readable, but it involves additional space for the string.

Functional Approach Using String Conversion

This approach also converts the number to a string but then leverages Rust's functional programming capabilities to check for palindromicity. By using chars().eq(chars().rev()), it compares the character sequence directly with its reversed version. This method is concise and leverages Rust's iterator and functional capabilities, providing a clear and elegant solution.

Extra Challenge: Imperative Version Using Math

The mathematical approach avoids converting the integer to a string, thus saving space. The idea is to construct the reversed number digit by digit from the original number. By repeatedly extracting the last digit of the original number (original % 10) and adding it to the reversed number (reversed = reversed * 10 + last_digit), we effectively build the reversed number. Then, we compare the reversed number with the original number to check for palindromicity. This approach is more efficient in terms of space but requires a good understanding of numerical manipulations.

Code

Imperative Approach Using String Conversion

    pub fn is_palindrome(x: i32) -> bool {
        	if x < 0 {
		return false;
	}

	let s = x.to_string();
	let bytes = s.as_bytes();
	let mut i = 0;
	let mut j = s.len() -1;

	while i < j {
		if bytes[i] != bytes[j] {
			return false;
		}
		i += 1;
		j -= 1;
	}
	true
    }

Functional Approach Using String Conversion

fn is_palindrome(x: i32) -> bool {
	if x < 0 {
		return false;
	}

    let x = x.to_string();
    x.chars().eq(x.chars().rev())
}

Extra Challenge: Imperative Version using Math

fn is_palindrome(x: i32) -> bool {
    if x < 0 {
        return false;
    }

    let mut original = x;
    let mut reversed = 0;

    while original > 0 {
        reversed = reversed * 10 + original % 10;
        original /= 10;
    }

    x == reversed
}

Explanation

Each approach to determining whether an integer is a palindrome highlights different programming techniques and considerations. Let's delve into the details of each version:

Imperative Approach Using String Conversion

pub fn is_palindrome(x: i32) -> bool {
    // negative check
    if x < 0 {
        return false;
    }

	// string converion
    let s = x.to_string();
    // byte conversion
    let bytes = s.as_bytes();
    // two pointers
    let mut i = 0;
    let mut j = s.len() - 1;

	// compare number pairs
    while i < j {
        if bytes[i] != bytes[j] {
            return false;
        }
        i += 1;
        j -= 1;
    }
    true
}

• Negative Check: The function immediately returns false for negative numbers since the minus sign would invalidate palindrome properties.
• String Conversion: The number is converted to a string to utilize character comparison. This allows an easy check from both ends towards the center.
• Byte Array: Conversion to a byte array (as_bytes()) allows for efficient indexing and comparison of characters.
• Two-Pointer Technique: Two indices (i and j) are used to compare characters from opposite ends of the string. If any pair of characters doesn't match, the function returns false. The loop continues until the indices meet or cross, confirming the number is a palindrome.

Functional Approach Using String Conversion

fn is_palindrome(x: i32) -> bool {
    // negative check

    if x < 0 {
        return false;
    }
    // convert x to a string
    let x = x.to_string();
    // compare `x` with `eq()` and reversed version of `x` with `rev()`
    x.chars().eq(x.chars().rev())
}

• Simplicity: This approach is more succinct, leveraging Rust's powerful iterator and functional programming features.
• Character Iterator: x.chars() creates an iterator over the characters of the string.
• Reverse Iterator: x.chars().rev() creates a reverse iterator, allowing direct comparison of the original character sequence with its reversed version.
• Equality Check: The eq method compares two iterators element by element. If all corresponding characters match, it confirms the palindrome property.

Follow-Up Challenge: Imperative Version Using Math

fn is_palindrome(x: i32) -> bool {
    // negative check
    if x < 0 {
        return false;
    }

    // define our variables to hold
    // our original version to manipulate
    // and our reveresed version to compare to
    let mut original = x;
    let mut reversed = 0;

    // while our original version is
    // greater than 0 we continue with
    // mathematical calculations
    while original > 0 {
        reversed = reversed * 10 + original % 10;
        original /= 10;
    }
    // compare `x` to the `reversed` version
    x == reversed
}

• In-Place Reversal: This method avoids string conversion, instead reversing the number mathematically. This is efficient in terms of memory usage.
• Digit Extraction and Reversal: The last digit of original is appended to reversed by first multiplying reversed by 10 (shifting it one decimal place up) and then adding the last digit of original.
• Original Number Modification: original is divided by 10 to remove the last digit, progressively shortening the number until all digits have been processed.
• Palindrome Check: The function compares the original number with the reversed number. If they match, the number is a palindrome.

Complexity Analysis

Imperative Approach Using String Conversion

• Time Complexity: (O(n)), where (n) is the number of digits in the integer. This is because the function iterates over each character of the string representation of the integer once.
• Space Complexity: (O(n)). The additional space comes from converting the integer to a string, which requires space proportional to the number of digits in the integer.

Functional Approach Using String Conversion

• Time Complexity: (O(n)). Similar to the imperative approach, it needs to iterate over each character to compare them.
• Space Complexity: (O(n)). The conversion of the integer to a string and the creation of the reverse iterator both contribute to the space used.

Imperative Version Using Math

• Time Complexity: (O(\log_{10}(x))), where (x) is the value of the integer. The number of digits in (x) is proportional to the logarithm of (x), and the loop iterates once for each digit.
• Space Complexity: (O(1)). This approach uses a fixed amount of space, only a few integers, regardless of the size of the input number.

Additional Information

When choosing between these approaches, consider the context of your application. If space efficiency is paramount, the mathematical approach is preferable. For readability and ease of understanding, string conversion methods might be more suitable.

Further Reading / References

To deepen your understanding of the concepts used in these solutions, you might explore the following topics:

• String Manipulation in Rust: Learn more about how strings work in Rust, including ownership, borrowing, and methods associated with string manipulation.
• Iterators and Closures in Rust: These are powerful features that allow for concise and expressive code, especially in functional-style programming.
• Number Theory Basics: Understanding how numbers can be manipulated, reversed, and analyzed is crucial in many algorithmic problems.

Conclusion

In this blog post, we explored three different approaches to solving the palindrome number problem in Rust, each illustrating a unique aspect of Rust's capabilities. From simple string manipulation to more complex mathematical solutions, Rust provides the tools and features to implement efficient and readable solutions. Whether you prefer the imperative or functional programming paradigm, Rust accommodates both styles, allowing us to leverage its powerful type system and safety guarantees to write high-quality code.

Remember, the best solution often depends on the specific requirements and constraints of your project. By understanding the trade-offs between different approaches, we can make informed decisions that balance performance, readability, and Rust's idiomatic practices.