Solution by phleg_matic


  • 2
    P

    Approach #1 Normal Approach [Makes a new copy of the original number in reversed order]

    Intuition

    Make a number by reversing digits of the original number and then compare with original number


    Algorithm

    • Initialize rev_num = 0
    • Loop while num > 0
    • (a) Multiply rev_num by 10 and add remainder of num (b) Divide num by 10
    • Compare num with rev_num if yes then num is palindrome

    Suppose we have a function `bool isPalindrome(int)` ....

    C++

    int isPalindrome(int num)
    {
        int rev_num = 0;
        int temp=num
        while (num > 0)
        {
            rev_num = rev_num*10 + num%10;
            num = num/10;
        }
        if (rev_num == temp)
          return true;
        else
          return false;
    }
    
    

    Complexity Analysis

    • Time complexity : O(Log(n)).
    • For calculating reverse of a number which is O(Log(n)) where n is input number.
    • Space complexity : O(n).
    • We need a variable to store num for temporary purpose and a variable to store reversed number.
    --- #### Approach #2 Space Efficient [Use Less Space]

    Intution


    Extract the first and last digit of number
    and compare them .

    Then second first and second last and compare them.

    And so on.....

    Algorithm

    • The concept of a palindromic number is that the number should read the same forwards and backwards.
    • Using this information, we can compare the first digit and the last digit.
    • Trick is, for the first digit, we need the order of the number.
    • Say, 12321. Dividing this by 10000 would get us the leading 1. The trailing 1 can be retrieved by taking the mod with 10.
    • Now, to reduce this to 232.
      (12321 % 10000)/10 = (2321)/10 = 232
    • And now, the 10000 would need to be reduced by a factor of 2.


    **C++**
    bool isPalindrome(int n)
    {
        int divisor = 1;
        while (n / divisor >= 10)
            divisor = divisor * 10;
        while (n != 0)
        {
            int leading = n / divisor;
            int trailing = n % 10;
    
            if (leading != trailing)  
                return false;
    
            n = (n % divisor) / 10;
            divisor = divisor / 100;
        }
        return true;
    }
    
    

    Complexity Analysis

    • Time complexity : O(n) .
      Time Complexity is same as of Approach 1.

    • Space complexity : Less space is used as we are not making any copy of our number and not storing it temporarily anywhere


Log in to reply
 

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