Problem
Abstract
To see a number is a palindrome number means it should be looked exactly the same with the origin when it got reversed.
For example: 121, 0
Additionally based on the Example 2, we need to consider negative numbers are not palindrome numbers.
Follow up message is solving the problem by trying not to convert to a string.
Solution - The String way
Code:
class Solution {
func isPalindrome(_ x: Int) -> Bool {
String(x) == String(String(x).reversed())
}
}
The workable way but not good for couple of reasons.
- During string conversions consumed certain number of resources.
- To able to be compared, the reversed string has to be converted back to a string.
Solution - Integer
Code:
class Solution {
func isPalindrome(_ x: Int) -> Bool {
// 1. Early exist
guard x >= 0 else { return false }
var origin = x
var reversed = 0
// 2. Routines
while origin != 0 {
reversed = reversed * 10 + origin % 10
origin = origin / 10
}
return reversed == x
}
}
Complexity
- Time Complexity: O(n)
nis length(number of digits) of the given integer.
- Space Complexity: O(1)
- reversed and origin as 1 and 1 → O(2) → O(1)
1. Early exist
To eliminate the negative number, I added a guard here
guard x >= 0 else { return false }
2. Routines
To reverse an integer, during every routine, we can use the previous reversed number times 10, plus current remainder of x divides by 10, then divide the x by 10 and save back to x, do the same thing until the x becomes 0.
For example, when given is 121, steps can be shown as following
// Initial state
x = 121
r = 0 // short for reversed
// === 1st run ===
// x is 121, NOT 0, entering the while loop
// r = r * 10 + x % 10
r = 1
// x = x / 10
x = 12
// === 2nd run ===
// x is 12, NOT 0, entering the while loop
// r = r * 10 + x % 10
r = 12 // 1 * 10 + 2 = 12 // 2 is from 12 % 10 = 2
// x = x / 10
x = 1 // 12 / 10 = 1
// === 3rd run ===
// x is 1, NOT 0, entering the while loop
// r = r * 10 + x % 10
r = 121 // 12 * 10 + 1 = 12 // 1 is from 1 % 10 = 1
// x = x / 10
x = 0 // 1 / 10 = 0
// === 4th run ===
// x is 0, NOT entering the while loop
// === End of the routine ===
Since x is immutable as a method parameter, we need a mutable variable var origin = x to do the job for us.
Solution - Integer (2)
guard x >= 0 else { return false }
The precondition can be merged to the while loop's, but for readability, I am a little bit concern because the condition could became not so observable.
Another reason I am not happy with this is I have to declare origin and reversed for negative numbers.
class Solution {
func isPalindrome(_ x: Int) -> Bool {
var origin = x
var reversed = 0
while origin > 0 { // Changed from origin != 0 to origin > 0
reversed = reversed * 10 + origin % 10
origin = origin / 10
}
return reversed == x
}
}
Solution - Integer - Going half way
Code:
class Solution {
func isPalindrome(_ x: Int) -> Bool {
// 1. Early exist
guard x >= 0, !(x % 10 == 0 && x != 0) else { return false }
var origin = x
var reversed = 0
// 2. Routine
while origin > reversed {
reversed = reversed * 10 + origin % 10
origin /= 10
}
// 3. Evaluate
return origin == reversed || origin == reversed / 10
}
}
Thought
What if we can only go the half way, it can saving time when the given is an enormous integer.
2. Routine
When origin > reversed means the number already passed the middle point.
3. Evaluate
- Determine by
origin == reversed
- When number of digits is even, eg.
1221
- When number of digits is even, eg.
- Determine by
origin == reversed / 10
- When number of digits is odd, eg.
121
- To able to compare, needs to remove the number in the middle.
- For example, Values of
originandreversedare1and12.
- When number of digits is odd, eg.
End of post
That's it!
Please leave comment if you have any comments, thanks for your reading!
SOCIAL SHARE CARD GENERATOR