# Solution by SoumyaroopRoy

• #### 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 `i`th 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 /= 10;
• Space complexity : \$\$O(n)\$\$, because `msd_mask` has at most `n` digits.