LeetCode in Swift - 9. Palindrome Number

Problem

• https://leetcode.com/problems/palindrome-number
• 中文 - https://leetcode.cn/problems/palindrome-number

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)
  • n is 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
• 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 origin and reversed are 1 and 12.

End of post

That's it!

Please leave comment if you have any comments, thanks for your reading!