Month: April 2021

https://leetcode.com/problems/palindrome-number/

So I was doing a few leetcode questions today. Honestly, I just found this one and it seemed interesting because it was easy, and it had multiple solutions to the problem. You could take multiple jabs at it from different angles. For example, you could simply do math operations on it and get the modulo of 10 of the number which would give you the last digit, or you could do string manipulation.

You could also create a stack and a queue of each value and do the modulo of 10 for each number and then compare the stack and queue values because of the FIFO/LIFO rules of these data structures. However, this is not only inefficient in time complexity, but also in space because we are creating two unnecessary data structures.

We could also just convert the number to a string and then compare each value from the ends, for example:

bool isPalindrome(int x) {
        string s = to_string(x);
        
        int len = s.size() - 1;
        int n = 0;
        
        while(n < len)
        {
            if (s[n] != s[len])
                return false;
            
            len--;
            n++;
        }
        
        return true;
    }

However, this solution is not very good either because we are converting the integer to a string, which I believe is an O(N) time complexity, because each character has to be individually converted to a number.

So I found another solution which basically takes advantage of how math works.

bool isPalindrome(int n)
{
    int original = n;
    
    int reversed = 0;
    
    while(n > 0)
    {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    
    if (original == reversed)
        return true;
    else
        return false;
}

This may not even be the most efficient solution as I may be ignorant on other mathematical concepts and how they work. However, given this, the math is simple. We know that n % 10 will give us the last digit in the number. So for example: 123 % 10 would give us 3.

Because we know this, we can simply loop through n, and say, while n is not 0, the reversed version of the number will be itself times 10 + the remainder (n % 10).

So given reversed = 0 for the first iteration of our loop, the math would be:
0 = 0 * 10 + 3

Obviously, this is assuming that n is 123. So after the first iteration, reversed will equate to 3. On the second iteration, after we divide x by 10, it would be:

3 = 3 * 10 + 2, which is 32, so reversed is now 32, which is obviously the first two digits in reverse of 123, it’s 32. If we do it again we will get the one. Let’s do it.

If we do n % 10 again, we get a remainder of 1, or our last digit. So then we take 32 = 32 * 10 + 1 which is 321. And there we go, we have the numbers in reverse. The last thing to do is to essentially check if the original value of n, is equal to this newly reversed value of n.

Return true if they are equal, return false otherwise.

Anyways, hopefully this helps other people who are trying to practice algorithms!