Check If The Number Is A Palindrome Problem Statement

An integer is called a Palindrome if it reads the same backward as forward.\ Given an integer, check whether it is a palindrome.

Example One

{
"num": 1234321
}

Reading the given number backward gives: 1234321.\ This is exactly the same as the input number. Thus, the number is a palindrome and we return true.

Output:

1

Example Two

{
"num": -1223
}

Reading the given number backward gives: 3221-.\ This is not equal to the input number. Thus, the number is not a palindrome and we return false.

Output:

0

Notes

Constraints:

• -2³¹ <= input number <= 2³¹ - 1

We have provided three solutions.

We will first start with a general brute force and will then move on to explore the other different approaches we can use to solve this problem. Throughout the editorial, we will refer to the input number as num and the number of digits in num as d( = log10num + 1).

Check If The Number Is A Palindrome Solution 1: Convert To String

An integer is called a Palindrome if it reads the same backward as forward.

So, we need to compare the first digit of the number with its last digit, second digit with its second last digit and so on.

Now, num being an integer and not a string, there is no direct way through which we can access the digit at any random location.

Hence, the simplest way that might come into your mind is to first convert the number into a string and then check whether that string is a Palindrome or not.

To convert an integer into a string, we can one-by-one extract the rightmost digit from the integer, add it to the string and then remove the rightmost digit from the integer. We will continue this till the number is greater than zero.

Let us say, we have num = 780.

• Step 1: We will call its string equivalent as str. Initially, str is empty. Hence, we have str = "" initially.
• Step 2: Now, since num is greater than zero, we will extract its rightmost digit as num % 10 (remainder when num is divided by 10) and add it to str. So, str now is "0".
• Step 3: Finally, we need to remove the rightmost digit from num. If you observe it carefully, the rightmost digit can be removed if we convert num to the quotient we get by dividing num by 10. Hence, num will now be converted to 780 / 10 = 78 (here, x / y is the result of floor division).
• Step 4: As stated before, we will continue this process till num > 0. This condition is still satisfied, hence we will follow the same sequence of operations. The rightmost digit in num is 78 % 10 = 8. Adding this to str gives us str = "08". Finally, num will be converted to 78 / 10 = 7.
• Step 5: Again, since 7 > 0, we will extract the rightmost digit in num as 7 % 10 = 7. Adding this to str gives us str = "087". Finally, num will be converted to 7 / 10 = 0.

Now, since num > 0 is no longer satisfied, we do not have to continue further.

Here if you observe, the string actually stores the reverse of the number. But, does it really matter? It does not.

Reason being, if the number is a palindrome, its reverse will also be a palindrome, as a palindrome is exactly the same as its reverse.

So, it does not matter whether we are checking for the number to be a palindrome or for its reverse to be a palindrome.

Now, as we have the string equivalent of the given number, checking it for being a palindrome is pretty straightforward.

Let us say, the length of the string formed is len.

We just need to compare str[0] with str[len - 1], then str[1] with str[len - 2] and so on.

Hence, we now have to iterate from index = 0 to len / 2 and check if str[index] is equal to str[len - index - 1] or not.

If the equality holds for all the values of the index in the given range, then the number is a palindrome. Else, it is not.

(Note that we need to iterate till len / 2 and not till len - 1 as we just need to compare the first half of the string with the second half).

Apart from these things, we can initially handle an edge case for negative numbers. If num is negative, we can return false as a negative number can never be a palindrome (even the reverse of -121 will be 121-).

Time Complexity

O(d).

We used an O(d) amount of time to extract all the digits from num and to finally check whether the string equivalent is a palindrome or not.

Auxiliary Space Used

O(d).

To store the string equivalent of the number.

Space Complexity

O(d).

Space used for input: O(1).

Auxiliary space used: O(d).

Space used for output: O(1).

So, total space complexity: O(d).

Code For Check If The Number Is A Palindrome Solution 1: Convert To String

/*
Asymptotic complexity in terms of the number of digits in \`num\`( = \`d\`) :
* Time: O(d).
* Auxiliary space: O(d).
* Total space: O(d).
*/

bool is_palindrome(int num) {
    // Edge case to handle the negative number case.
    if (num < 0) {
        return false;
    }

    string str = "";
    int digit;

    while (num > 0) {
        digit = num % 10; // Extracting the rightmost digit of the number.

        str += ('0' + digit); // Adding the rightmost digit to our string.

        num /= 10; // Removing the rightmost digit from the number.
    }

    // Checking if the formed string is a palindrome or not.
    int len = str.length();
    for (int i = 0; i < len / 2; ++i) {
        if (str[i] != str[len - i - 1]) {
            return false;
        }
    }

    return true;
}

Check If The Number Is A Palindrome Solution 2: Extract The Second Half

As you can observe in the above solution, the extra space is just because we are converting the number into a string. So, if by any technique, we are able to avoid the string construction, we can avoid this extra space as well.

If we go by definition, a number is called a palindrome if it is exactly equal to its reverse. So, how about generating the reverse of the number in the form of an integer and then comparing it with the original number?

This seems to be a good idea but may not work well for some test cases.

For example, what if the reverse of that number overflows to fit in a standard 32-bit integer?

If we have num = 1999999999, then its reverse will be equal to 9999999991. Here, although num fits well in a standard 32-bit integer, its reverse clearly does not.

Hence, it is not a good idea to convert the number into its reverse.

Let us look at an interesting observation regarding palindromes.

Consider we have num = 123321. For this to be a palindrome, the reverse of the second half of the number should be the same as the first half. If we reverse the second half of num, we will have 123123. Here, as you can observe, both the halves are exactly the same.

So, if we somehow extract out the second half of the given number, reverse it, and then compare it with the first half, we are pretty much done. Here, we do not even need to worry about the possible integer overflows as we are reversing only half of the digits of the given number.

In case when the number has an odd number of digits, we can ignore the middle digit.

Now, how will you extract the second half? The approach is almost the same that we used to generate the string equivalent of the given number.

For example, consider that we have num = 123321. Let us make the changes in num so that finally, num represents the first half and an integer sec_half stores the second half. Initially, sec_half = 0.

Now, we will keep extracting the rightmost digit in num and will keep updating that digit in the sec_half.

We will continue this till num > sec_half. Hence, finally num will either have the same number of digits as sec_half (if num had even number of digits originally) or num will have one digit less than sec_half (if num had odd number of digits originally).

Note that we do not need to explicitly reverse the sec_half as this technique, by default generates the reverse (as we observed in the string approach).

For example, if num initially was 123321, then finally we will have:

num = 123 and sec_half = 123

Here, num == sec_half will signify that num was originally a palindrome.

Or, if num initially was 12321, then we will finally have:

num = 12 and sec_half = 123

Here, num == (sec_half / 10) will signify that num was originally a palindrome.

Do you see any loopholes in the approach?

Apart from the edge case for negative numbers, there is one more special case we will have to consider here.

Let us understand it with an example. Consider num = 1100.

In this case, if we follow the same approach, we will finally have:

num = 1 and sec_half = 001 = 1

Now, since num == sec_half, our approach will return true. But, 1100 is clearly not a palindrome!

Where did we fail?

We actually ignored the fact that our solution will ignore the trailing zeros in the number. Ideally, this should not be the case.

Hence, we will have to handle this base case separately that if num % 10 is initially 0 and num != 0, we directly return false.

Time Complexity

O(d).

We use O(d) amount of time to extract the half of the digits from num.

Auxiliary Space Used

O(1).

Space Complexity

O(1).

Space used for input: O(1).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(1).

Code For Check If The Number Is A Palindrome Solution 2: Extract The Second Half

/*
Asymptotic complexity in terms of the number of digits in \`num\`( = \`d\`) :
* Time: O(d).
* Auxiliary space: O(1).
* Total space: O(1).
*/

bool is_palindrome(int num) {

    if (num == 0) {
        return true;
    }

    // A negative number can never be a Palindrome.
    // Also, if a positive number has trailing zeros, it cannot be a palindrome.
    if (num < 0 or num % 10 == 0) {
        return false;
    }

    int sec_half = 0;
    int digit;

    while (num > sec_half) {
        digit = num % 10; // Extracting the rightmost digit.

        sec_half = sec_half * 10 + digit; // Adding that digit in sec_half.

        num /= 10; // Removing the rightmost digit from the number num.
    }

    // Now, if num originally had even number of digits, then both num
    // and sec_half will now have same number of digits and thus, num == sec_half
    // must satisfy for num originally being a palindrome.
    // Else, if num originally had odd number of digits, then num will have one
    // digit less than the sec_half and thus, num == sec_half / 10 must satisfy
    // (as we can ignore the middle digit while checking for palindrome)
    return (num == sec_half or num == sec_half / 10);
}

Check If The Number Is A Palindrome Solution 3: Check Without Reversing

The approach we just discussed takes O(d) time and O(1) extra space. So, although we cannot further improve upon the time and space complexity, there is another interesting approach to solve this question that does not require you to even reverse the digits of the number.

At the starting of this editorial, we mentioned that there is no direct way through which we can access the random digits in an integer.

But, with a little mathematical tweak, we actually can even do this!

Let us understand how.

Carefully observe the following statements:

If num = 12345,

the first digit of num is: (num / 10000) % 10 = 1

the second digit of num is: (num / 1000) % 10 = 2

the third digit of num is: (num / 100) % 10 = 3

the fourth digit of num is: (num / 10) % 10 = 4

the fifth digit of num is: (num / 1) % 10 = 5

Did you see a pattern?

The i-th digit in num is: num / 10d - i% 10

Hence, the random access can be done even in integers! Using the above equation, we can get any i-th digit in num and the rest of the checks remain the same as we did for a string.

That is, the first digit should be compared with the last digit, second digit with second last digit and so on.

Time Complexity

O(d).

We do O(d) number of comparisons and each comparison takes O(1) time.

Auxiliary Space Used

O(1).

Space Complexity

O(1).

Space used for input: O(1).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(1).

Code For Check If The Number Is A Palindrome Solution 3: Check Without Reversing

/*
Asymptotic complexity in terms of the number of digits in \`num\`( = \`d\`) :
* Time: O(d).
* Auxiliary space: O(1).
* Total space: O(1).
*/

bool is_palindrome(int num) {
    // Edge case to handle the negative number case.
    if (num < 0) {
        return false;
    }

    // If the number is zero, it is a palindrome.
    if (num == 0) {
        return true;
    }

    int num_of_digits = log10(num) + 1; // Number of digits in num.
    int div1 = pow(10, num_of_digits - 1); // Divisor to extract the leftmost digit.
    int div2 = 1; // Divisor to extract the rightmost digit.

    for (int i = 0; i < num_of_digits / 2; i++) {
        // If both the digits are not same, the number is not a palindrome.
        if ((num / div1) % 10 != (num / div2) % 10) {
            return false;
        }

        div1 /= 10; // Next, we will have to check for the digit towards right.
        div2 *= 10; // Next, we will have to check for the digit towards left.
    }

    return true;
}

We hope that these solutions to palindrome number problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.