LeetCode Problem : Palindrome Number

Problem Statement

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

Intuition

How to revert integer number? How to approach this problem without even converting into string?

Approach

integer 121 for example,

121 / 10 = 12
121 % 10 = 1 , let this be 'a' 

12 / 10 = 1
12 % 10 = 2 , let this be 'b' 

1 / 10 = 0
1 % 10 = 1 , let this be 'c'

reverted number is (((a*10) + b)10 + c)

But here we want to revert only half because the range of the given input number is between -2^31 and 2^31. That is 2147483648 and if we try to revert this number entirely, int type can not even hold this value since the least significant digit is greater than the most significant digit. Therefore what we want to do is to revert only half of it. We can do this by making sure building-reverted number is less than the original number repeatly being divided by 10. For example, consider integer 1234, there will be comparison 4 vs 123 than 12 vs 43 and this is the exact condition we want to stop.

When the length of input is odd, we can simply do comparison between building-reverted number divided by 10 is equal to the original 'getting-smaller' number.

Lastly we want to handle following edge cases.
- Negative number -> always not palindrome
- 0 -> always palindrome
- number multiple of 10 -> always not palindrome

Time Complexity

• O(log10 N) : Every iteration we divide the number by 10

Code

func isPalindrome(x int) bool {
    var rev int
    if x < 0 || (x % 10 == 0 && x!= 0){
        return false
    }
    if x < 10 {
        return true
    }

    for x > rev {
        rev = rev*10 + (x%10)
        x = x/10
    }
    if x == rev || rev/10 == x {
        return true
    }
    return false
}

Can We Do Better?

No, O(logN) is already good enough

Seed For Interview

Revert half of the number and be careful about few edge cases.