Solution by SoumyaroopRoy


  • 0
    S

    General Note

    All negative inputs are considered non-palindromic because the negative sign ('-') is considered a part of the input's textual representation.

    Approach #1 Brute Force: Operate on Strings [Accepted]

    Intuition

    Construct the reverse of the input number and compare if that is the same as the input.

    Algorithm

    The simplest implementation is to convert the input number to string and then reverse a copy of the string to compare. This is because reversing a string is easier than reversing an integer.

    C++

    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
    
        string str = to_string(x);
        string rev_str(str.crbegin(), str.crend());
        return str == rev_str;
    }
    

    Other ways to create rev_str are:

    string rev_str(str);
    reverse(rev_str.begin(), rev_str.end());
    

    and

    string rev_str;
    reverse_copy(str.begin(), str.end(), back_inserter(rev_str));
    

    among others.

    Complexity Analysis

    • Time complexity : $$O(n)$$, where $$n$$ is the number of digits in the input, but there are multiple passes on the input:
      • First time in the to_string() call
      • Second time while creating rev_str
      • Third time while performing the string comparison using the == operator
    • Space complexity : $$O(n)$$. Two strings of size $$n$$ are being constructed. The second string may be avoided by converting the reversed string back to integer.

    Approach #2 Brute Force: Operate on Integers [Accepted]

    Intuition

    The approach is the same as the one above. However, the implementation is different in that the reverse of the input is created from the input as an integer instead of a string.

    Algorithm

    Iterate on the digits of the input number from right to left and add them to the reversed number in left to right order. Here are the steps to achieve this:

    1. Divide the input number by 10 to extract the rightmost digit and set the input number to the quotient for the next iteration
    2. Multiply the reversed number by 10 to shift the digits left by 1 position and add the rightmost digit from the input number extracted in the previous step
    3. Continue the two steps above till the input number is 0

    Example: For 234 as input, initialize reversed to 0

    1. extracted_digit = 234 % 10 = 4, reversed = 10*0 + 4 = 4, input = 234 / 10 = 23
    2. extracted_digit = 23 % 10 = 3, reversed = 10*4 + 3 = 43, input = 23 / 10 = 2
    3. extracted_digit = 2 % 10 = 2, reversed = 10*43 + 2 = 432, input = 2 / 10 = 0

    C++

    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
    
        int rev_x = 0, x_copy = x;
        while (x) {
            rev_x *= 10;
            rev_x += x % 10;
            x /= 10;
        }
    
        return rev_x == x_copy;
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$, where $$n$$ is the number of digits in the input. This time there is only one pass on the input, during the creation of rev_x from x. Although, technically, the equality check at the end is also $$O(n)$$ but, on most CPUs, it maps to a single-cycle assembly instruction.
    • Space complexity : $$O(n)$$. Two integers -- one for rev_x and the other for x_copy -- of size $$n$$ digits are being constructed. This is more space efficient than creating two $$n$$ long strings.

    Approach #3 Improved: Operate on a String [Accepted]

    Intuition

    As in Approach #1, construct a string from the input number. But instead of reversing the string for comparison later, compare the first half of the string with the second half in reverse order.

    For instance, if string s constructed from the input integer is of size 6, compare s[0-2] with s[5-3]. As an example, if s were "853358", s[0-2] and s[5-3] are both "853"

    For a string of odd length, leave the middle character from the comparison. For example, if s were "23432", compare s[0-1], "23", to s[4-3], "23".

    Algorithm

    In principle, use two pointers or indices:

    1. One that traverses the string left to right from the start of the string to the middle of the string
    2. The other that traverses the string right to left from the end of the string to the middle of the string

    Since the length of the string is known is advance, this can be achieved by having just the first pointer (index) above and subtracting it from the string length to obtain the other.

    Example: For "853358" as s, string length 6,

    1. left_index = 0 gives right_index = (6 - 1) - 0 = 5
    2. left_index = 1 gives right_index = (6 - 1) - 1 = 4
    3. left_index = 2 gives right_index = (6 - 1) - 2 = 3

    C++

    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
    
        string str = to_string(x);
        for (int i = 0, n = str.size(); i < n / 2; ++i)
            if (str[i] != str[n - 1 - i])
                return false;
        return true;
    }
    

    The for-loop and the subsequent return statement above can also be replaced by the std::mismatch() function template, which compares two ranges and returns the points in those ranges where the first mismatch occurs, in C++ standard library:

    auto mid = str.cbegin() + str.size() / 2;
    return mismatch(str.cbegin(), mid, str.crbegin()).first == mid;
    

    Complexity Analysis

    • Time complexity : $$O(n)$$, where $$n$$ is the number of digits in the input, with two passes on the input -- once during the to_string() call and the other during the comparison phase (in the for-loop or in the mismatch() call).
    • Space complexity : $$O(n)$$. One string of size $$n$$ is being used as auxiliary space.

    Approach #4 Improved: Operate only on the Input [Accepted]

    Intuition

    The idea is similar to Approach #3 in that the the first half of the number is compared with the second half in reverse order. No auxiliary string is needed.

    Algorithm

    As noted in Approach #2, the least significant digit (LSD) of a number can be extracted by dividing by 10 and taking the remainder. The most significant digit (MSD) is obtained by dividing the number by the maximum power of 10 that is less than the number and taking the quotient. The maximum power of 10 that is less than the number is 1 followed by $$(n - 1)$$ 0's, where $$n$$ is the number of digits.

    Examples are:

    • 12345 has 5 digits; 10 ^ (5 - 1) = 10000; MSD of 12345 is 12345 / 10000 = 1
    • 3659 has 4 digits; 10 ^ (4 - 1) = 1000; MSD of 3659 is 3659 / 1000 = 3
    • 3 has 1 digit; 10 ^ (1 - 1) = 1; MSD of 3 is 3 / 1 = 3

    The next challenge is to choose the ith and (n - 1 - i)th iteration during iteration i. Recall the for-loop structure from Approach #3 above:

    for i = 0 to num_digits / 2
        if digit[i] != digit[n - 1 - i]
            return false
    return true
    

    This can be achieved by stripping off the LSD and MSD off x in each iteration in preparation for the next iteration.

    Putting it all together, the final steps are:

    1. Compute the number of digits n by taking the $$\floor(log_{10}(x))$$
    2. Initialize msd_mask as $$10^{n - 1}$$
    3. Repeat the following steps $$\floor(n/2)$$ times
    • Compute LSD as x module 10 and MSD as x div msd_mask
    • If LSD and MSD are not equal return false
    • Remove MSD from x by computing x modulo msd_mask
    • Remove LSD from x by computing x div 10
    • Set msd_mask to msd_mask div 100 since x now has 2 fewer digits
    1. If the program control reaches here, return true

    C++

    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
    
        int n = static_cast<int>(floor(log10(x)) + 1);
        int msd_mask = static_cast<int>(pow(10, n - 1));
        for (int i = 0; i < n / 2; ++i) {
            if (x / msd_mask != x % 10)
                return false;
            x %= msd_mask;
            x /= 10;
            msd_mask /= 100;
        }
        return true;
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$, where $$n$$ is the number of digits in the input, with only a single pass on the input.
    • Space complexity : $$O(n)$$, because msd_mask has at most n digits.

Log in to reply
 

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