Solution by costinbusioc


  • 1
    C

    Approach #1 Reverse the number [Accepted]

    Intuition

    Reverse the number and check for the two values to be the same.

    Algorithm

    • checking the value to be positive. A negative number is not palindrome
    • getting each last digit of the number and add it to the previous number multiplied by 10

    Java

    class Solution {
        public boolean isPalindrome(int x) {
    
            if (x < 0)
                return false;
    
            int rev = 0;
            int tmp = x;
    
            while (tmp != 0) {
                rev = rev * 10 + tmp % 10;
                tmp /= 10;
            }
    
            return x == rev;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(log n)$$.
      The number is divided by 10 each time.

    • Space complexity : $$O(1)$$.


    Approach #2 Comparing pair digits [Accepted]

    Intuition

    Although approach #1 is an accepted solution, there is a problem and that's the possibility of overflowing in which case the behavior depends on the language and for example for C/C++ is undefined.

    A better approach, would be that on the original number to compare the digits one by one on their corresponding positions. This can be done either by starting from the middle of the number, or compare from the two ends.
    That can be done by creating a mask (10 ^ n), where n is the number of digits for the number. Why so?

    Because this way, by dividing the number with the mask, we'll get the first digit, and by applying a "%10" operation, we'll get the last one. Perfect way to compare the two digits.
    To proceed on the next pair, we have to delete the last digit of the number, and divide the mask by 100 (one for the previous digit and one for the next one).

    Algorithm

    • building the initial mask
    • getting the left and right most digits and compare them
    • on different digits stop
    • on same digits, update the mask and the number and continue

    Java

    class Solution {
        public boolean isPalindrome(int x) {
    
            if (x < 0)
                return false;
    
            int div = 1;
    
            while (x / div >= 10) {
                div *= 10;
            }
    
            while (x != 0)
            {
                int leftDigit = x / div;
                int rightDigit = x % 10;
    
                if (leftDigit != rightDigit)
                    return false;
    
                x = (x % div) / 10;
    
                div /= 100;
            }
            return true;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(log n)
      To find the initial mask, we need to iterate through all the digits.

    • Space complexity : $$O(1)$$.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.