leetcode_rust/problems/p000_0xx/p000_009.rs
1//! # Description
2//!
3//! Given an integer `x`, return `true` if `x` is a
4//! palindrome, and `false` otherwise.
5//!
6//! Example 1:
7//!
8//! ```plain
9//! Input: x = 121
10//! Output: true
11//! Explanation: 121 reads as 121 from left to right and from right to left.
12//! ```
13//!
14//! Example 2:
15//!
16//! ```plain
17//! Input: x = -121
18//! Output: false
19//! Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
20//! ```
21//!
22//! Example 3:
23//!
24//! ```plain
25//! Input: x = 10
26//! Output: false
27//! Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
28//! ```
29//!
30//! Constraints:
31//!
32//! $-2^{31} \leqslant x \leqslant 2^{31} - 1$
33//!
34//! Follow up: Could you solve it without converting the integer to a string?
35//!
36//! Source: <https://leetcode.com/problems/palindrome-number/>
37
38////////////////////////////////////////////////////////////////////////////////
39
40/// Check if a given input is a palindrome number
41///
42/// # Arguments
43/// * `x` - input number
44///
45/// # Examples
46/// ```
47/// use leetcode_rust::problems::p000_0xx::p000_009::is_palindrome;
48///
49/// assert!(is_palindrome(12321) == true);
50/// assert!(is_palindrome(-12321) == false);
51/// ```
52pub fn is_palindrome(number: i32) -> bool {
53 // alg_1(number)
54 alg_2(number)
55}
56
57/// Algorithm 1: check digits using double-sided queue.
58///
59/// # Arguments
60/// * `number` - input number to check
61#[allow(dead_code)]
62fn alg_1(mut number: i32) -> bool {
63 if number < 0 {
64 return false;
65 }
66 let mut temp: Vec<i32> = vec![];
67
68 while number >= 10 {
69 temp.push(number % 10);
70 if number >= 10 {
71 number = number / 10;
72 }
73 }
74 temp.push(number);
75
76 if temp.len() == 2 {
77 return temp[0] == temp[1];
78 }
79
80 let mut idx_start = 0;
81 let mut idx_end = temp.len() - 1;
82
83 loop {
84 if idx_end == idx_start {
85 return true;
86 }
87
88 if idx_end - idx_start == 1 {
89 return temp[idx_end] == temp[idx_start];
90 }
91
92 if temp[idx_end] != temp[idx_start] {
93 return false;
94 }
95 idx_end -= 1;
96 idx_start += 1;
97 }
98}
99
100/// Algorithm 2: check digits fast subtraction.
101///
102/// # Arguments
103/// * `number` - input number to check
104#[allow(dead_code)]
105fn alg_2(mut number: i32) -> bool {
106 if number < 0 {
107 return false;
108 }
109
110 // One digit shorter than actual length.
111 let mut digits = (number as f32).log10().floor() as usize;
112 if digits == 0 {
113 return true;
114 }
115
116 loop {
117 number = (number - (number % 10) * 10i32.pow(digits as u32)) / 10;
118 if number < 0 || digits <= 1 {
119 break;
120 }
121
122 digits -= 2;
123 }
124
125 number == 0
126}