Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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

```
{
"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
```

```
{
"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
```

Constraints:

- -2
^{31}<= input number <= 2^{31}- 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`

( = `log`

_{10}`num + 1`

).

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-).

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.

O(d).

To store the string equivalent of the number.

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).

```
/*
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;
}
```

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 123**123**. 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.

O(d).

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

.

O(1).

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).

```
/*
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);
}
```

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 / 10`

^{d - 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.

O(d).

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

O(1).

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).

```
/*
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.

Note: Input and Output will already be taken care of.

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

```
{
"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
```

```
{
"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
```

Constraints:

- -2
^{31}<= input number <= 2^{31}- 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`

( = `log`

_{10}`num + 1`

).

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-).

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.

O(d).

To store the string equivalent of the number.

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).

```
/*
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;
}
```

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 123**123**. 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.

O(d).

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

.

O(1).

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).

```
/*
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);
}
```

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 / 10`

^{d - 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.

O(d).

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

O(1).

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).

```
/*
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.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart