Palindrome Number
January 4, 2012 in Uncategorized
Determine whether an integer is a palindrome. Do this without extra space.
Online Judge
This problem is available at Online Judge. Head over there and it will judge your solution. Currently only able to compile C++/Java code. If you are using other languages, you can still verify your solution by looking at the judge’s test cases and its expected output.
In previous posts (Longest Palindromic Substring Part I, Part II) we have discussed multiple approaches on finding the longest palindrome in a string. In this post we discuss ways to determine whether an integer is a palindrome. Sounds easy?
Hint:
Don’t be deceived by this problem which seemed easy to solve. Also note the restriction of doing it without extra space. Think of a generic solution that is not language/platform specific. Also, consider cases where your solution might go wrong.
Solution:
First, the problem statement did not specify if negative integers qualify as palindromes. Does negative integer such as -1 qualify as a palindrome? Finding out the full requirements of a problem before coding is what every programmer must do. For the purpose of discussion here, we define negative integers as non-palindromes.
The most intuitive approach is to first represent the integer as a string, since it is more convenient to manipulate. Although this certainly does work, it violates the restriction of not using extra space. (ie, you have to allocate n characters to store the reversed integer as string, where n is the maximum number of digits). I know, this sound like an unreasonable requirement (since it uses so little space), but don’t most interview problems have such requirements?
Another approach is to first reverse the number. If the number is the same as its reversed, then it must be a palindrome. You could reverse a number by doing the following:
1 2 3 4 5 6 7 8 9 | int reverse(int num) { assert(num >= 0); // for non-negative integers only. int rev = 0; while (num != 0) { rev = rev * 10 + num % 10; num /= 10; } return rev; } |
This seemed to work too, but did you consider the possibility that the reversed number might overflow? If it overflows, the behavior is language specific (For Java the number wraps around on overflow, but in C/C++ its behavior is undefined). Yuck.
Of course, we could avoid overflow by storing and returning a type that has larger size than int (ie, long long). However, do note that this is language specific, and the larger type might not always be available on all languages.
We could construct a better and more generic solution. One pointer is that, we must start comparing the digits somewhere. And you know there could only be two ways, either expand from the middle or compare from the two ends.
It turns out that comparing from the two ends is easier. First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.
Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought. I will leave this to you as an exercise. Please think your solution out before you peek on the solution below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | bool isPalindrome(int x) { if (x < 0) return false; int div = 1; while (x / div >= 10) { div *= 10; } while (x != 0) { int l = x / div; int r = x % 10; if (l != r) return false; x = (x % div) / 10; div /= 100; } return true; } |
Alternative Solution:
Credits go to Dev who suggested a recursive solution (if extra stack space does not count as extra space), which is pretty neat too.
1 2 3 4 5 6 7 8 9 10 11 12 13 | bool isPalindrome(int x, int &y) { if (x < 0) return false; if (x == 0) return true; if (isPalindrome(x/10, y) && (x%10 == y%10)) { y /= 10; return true; } else { return false; } } bool isPalindrome(int x) { return isPalindrome(x, x); } |
Dev said on January 5, 2012
Above code uses Stack memory
ps: -ve case are not handled
1337c0d3r said on January 5, 2012
Pretty cool way of utilizing recursion, and this works too.
By the way this conditional:
could be replaced by:
ChineseBalckTea said on April 8, 2012
Anyone can explain how this recursion works? Thanks.
ChineseBalckTea said on April 8, 2012
Opps… Understand now, used one sample to draw the call stack to figure it out.
Krishna Teja said on May 26, 2012
Hi Dev, i would appreciate if you could answer my questions.
(a) What is the logical significance of parameters x and y.
(b) Ideally we should have only one parameter to check if the number is palindrome or not, is it not ?
Will Ness said on June 5, 2012
I’m no Dev, but what his function does, is ingeniously arranging for the number to be scanned in both directions on the way back up from the deepest level of recursion. That’s why two parameters are used.
Notice the second one is a reference, to the outermost “x”. On the way down the recursion, stack frames are created, each holding (1). its own var named “x” which is progressively divided into by 10; and (2). a reference “y” to the original “x”. Initially all “y”s in all the stack frames – which are all references to the same outer “x” – have the same value, the original “x”. Now on the way back up, “y” is divided into by 10 – thereby changing the value of all the “y”s at the same time (which are all references to the same outer “x”).
When the deeper-level invocation divides its “y” by 10 before returning to the upper-level invocation, that upper-level invocation finds its “y” divided by 10. And this is done in the reversed order. So when moduli are compared, they calculate their digits from either end, respectively.
Ingenious.
wood said on January 6, 2012
How about checking the binary format? If the binary result is the same when reading from left to right and from right to left, except leading zero bits, the number is palindrome.
Thus reverse bits and then check as follows:
int v = num; // num is input
int r = 0;
do{
r < > = 1;
} while ( v )
return r == num;
wood said on January 6, 2012
code in do loop is :
r equals to its left shift by 1;
r equals to it OR with (v AND 1);
v equals to its right shift by 1;
1337c0d3r said on January 6, 2012
Consider the binary representation of 17 –> “10001″. Its binary representation is a palindrome, but 17 itself as a number is not.
wood said on January 6, 2012
yes, you’re correct. They are different questions.
worker1137 said on January 8, 2012
I came up with an alternative solution using logs to peel off the most significant digit; it is certainly slower than the alternatives, but it does highlight some interesting log properties.
public boolean isPalindrome(int value) {
if (value =0 ) return true;
if (value = 10) {
int mostSig = 0;
int leastSig = 0;
leastSig = tempValue % 10;
double temp = tempValue;
double logValue = Math.log10((double)tempValue);
while (Math.log10(temp) >= Math.floor(logValue)) {
mostSig++;
temp -= Math.pow(10, Math.floor(logValue));
}
if (leastSig != mostSig) return false;
tempValue = (int)temp;
tempValue /= 10;
}
return true;
}
worker1137 said on January 8, 2012
hmm that did not paste properly, trying one more time:
public boolean checkPalindromeInt(int value) {
if (value = 10) {
int mostSig = 0;
int leastSig = 0;
leastSig = tempValue % 10;
double temp = tempValue;
double logValue = Math.log10((double)tempValue);
while (Math.log10(temp) >= Math.floor(logValue)) {
System.out.println(“logValue: ” + Math.log10(temp));
mostSig++;
temp -= Math.pow(10, Math.floor(logValue));
}
System.out.println(mostSig + ” ” + leastSig);
if (leastSig != mostSig) return false;
tempValue = (int)temp;
tempValue /= 10;
}
return true;
}
Ratna said on January 21, 2012
bool checkPalindrome(int a)
{
int x = a;
int y = 0 ;
for(;a;a=a/10)
{
y = y*10 + a%10;
}
return (x==y);
}
Balaji said on January 24, 2012
What if we reverse the given number and then check if the reversed number is equal to the original number?
bool isPalindrome(int i){
int temp = i, reversed=0;
//loop to reverse the number
while(temp!=0){
reversed= reversed*10+(temp%10);
temp= temp/10;
}
if(reversed == i) return true;
else return false;
}
Balaji said on January 24, 2012
oops.. another friend above has posted the same solution.. I’m sorry
ydx said on February 12, 2012
bool isPalindrome(int x) {
if (x = 10) {
div *= 10;
}
while (x != 0) {
int l = x / div;
int r = x % 10;
if (l != r) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
this is not right
it is failed the assert(isPalindrome(10111));
Harish said on February 14, 2012
hi, your code has faults,you are assigning 10 to x instead of comparing it to 10 and div seems to be not declared.
SK said on February 16, 2012
a number is a palindrome if it is multiple of 11..(i.e. for numbers having more than i digit) and single digit numbers are palindromes
lavin said on February 18, 2012
check 132.
raghavg said on February 27, 2012
cant we use x/div!=1 instead of x/div>=10 in first alternative solution….
Caopeng said on February 29, 2012
Mine:
bool isPalindrome(int x) {
if ( x = 10 ; y /= 10, w *= 10)
;
for (; w >= 10; w /= 100) {
if (x / w != x % 10) {
return false;
}
x -= x / w * w;
x /= 10;
}
return true;
}
Caopeng said on February 29, 2012
Mine:
if ( x = 10 ; y /= 10, w *= 10)
;
for (; w >= 10; w /= 100) {
if (x / w != x % 10) {
return false;
}
x -= x / w * w;
x /= 10;
}
return true;
victor said on March 5, 2012
public boolean ispalin(int x){
if(x == 0){
return true;
}else if(x < 0){
return false;
}else{
int digit = (int) Math.floor(Math.log10(x));
int pow = (int) Math.pow(10, digit);
int high = (int) Math.floor( x/ (pow));
int low = x % 10;
if(high == low){
return ispalin( (x-high*(pow))/10 );
}else{
return false;
}
}
}
PhillyCheeseSteak said on March 6, 2012
Any comments about the performance of this Python code?
def isPalindrome(x):
if (x 10):
y = y/10
i=i+1
if(unit != y):
return False
return isPalindrome(((x-unit*pow(10,i))-unit)/10)
PhillyCheeseSteak said on March 6, 2012
def isPalindrome(x):
if (x 10):
y = y/10
i=i+1
if(unit != y):
return False
return isPalindrome(((x-unit*pow(10,i))-unit)/10)
PhillyCheeseSteak said on March 6, 2012
I have no clue why the code isn’t pasting correctly.
hari said on March 25, 2012
Admin,
The below link does not work. can you please take a look?
http://www.leetcode.com/category/amazon-interview
p1999 said on April 3, 2012
Hi, I took “no extra space” to literally mean no stack space / heap space, so, assuming log10 and pow10 does the operations with registers, this is a real solution:
p1999 said on April 3, 2012
Sorry, the code didn’t paste correctly. Here we go again:
Kircheis He said on April 27, 2012
I am not sure whether the usage of int l and r in Solution Part really means “no extra space used”.
Actually, I can’t think of a way that uses absolutely “no extra space”.
hwl said on May 20, 2012
I first came up with the solution that could have overflow. Then I realize I can
still use it but cut the execution by half and no overflow issue.
The basic idea is multiply the newNum by 10 while dividing the input num by 10 but
stop when newNum>num.
bool isPal(int num) {
if (nnewNum) {
newNum = newNum*10+num%10;
if (newN==origN || newN*10 == origN)
return true;
rigN = origN/10;
}
return false;
}
darksteel said on May 21, 2012
Here’s my solution. It uses the similar idea which hwl proposed but seems he didn’t give the exact code:
silyt said on April 16, 2013
I think this is the best solution for now.
Amit Singh said on July 22, 2012
length=0;
num=n; // num is copy of original value of n
this method was an easy one and is passing in all cases – - – - – - – -
while(num>0)
{
num/=10;length++;
}
for(p=length-1,q=0;p>q;p–,q++)
if(n/pow(10,p)-n/pow(10,q)!=10*(n/pow(10,p+1)-n/pow(10,q+1)) )
break;
Prateek Caire said on August 19, 2012
Thanks. Try whether Linked list is palindrome?
Prateek Caire said on August 19, 2012
Sergey said on October 17, 2012
What about having following two functions
int size(int number); //returns number of digits in a given number
int getDigitAt(int number, int index);
now you can test if it is a palindrome like you would do with a string
boolean isPolyndrome(int number) {
if (number < 0) return false;
int size = size(number);
for (int i = 0; i < size/2; i++) {
if (getDigitAt(number, i) != getDigit(number, size-1-i) { return false; }
}
return true;
}
I also not clear on "no extra space part". Does it mean I can not even use local variables?
Mounica said on November 1, 2012
Hi,
Please someone explain me why the reverse number might overflow? we are passing num as “int” and storing reverse as “rev” in an int. Then, why will reverse overflow?
zd987 said on November 7, 2012
a largest 32-bit int is 2147483647, which will overflow if reversed.
Mounica said on November 20, 2012
thanks.. it was bugging me
Rajesh Patidar said on November 12, 2012
it took me 3 year to understand this piece of code , but hell yeah, finally its done
shoubhik said on November 17, 2012
how abt this code in java. it is non recursive
Niubility said on January 16, 2013
Niubility said on January 16, 2013
the condition of second while loop shall be (j < length / 2)
CodeSCV said on January 19, 2013
here is a solution that do not use recursion and solves it in o(length(x)) time.
class Solution {
public:
bool isPalindrome(int x) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (x right) {
right = right * 10 + left % 10;
left /= 10;
} else {
// left < right
return false;
}
}
}
};
CodeSCV said on January 19, 2013
Raj said on January 20, 2013
Here is solution the best and easy solution I can say..Please let me know..If I am wrong
#include
using namespace std;
int reverse(int num) {
assert(num >= 0); // for non-negative integers only.
int rev = 0;
while (num != 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}
int Calculate(int n){
int lValue=1;
while(n){
lValue=lValue*10;
n–;
}
return lValue;
}
bool IsPalindrom(int iNumber){
if(iNumber<0)
iNumber = iNumber*-1;
int lValue =0;
lValue = iNumber;
int lNumberOfdigit=0;
while(lValue){
lNumberOfdigit++;
lValue =lValue/10;
}
int lFuture = lNumberOfdigit;
lNumberOfdigit = lNumberOfdigit/2;
if( 0 == lFuture%2){
int lLeft = iNumber/Calculate(lNumberOfdigit);
int lRight =iNumber%Calculate(lNumberOfdigit);
if(lLeft == reverse(lRight))
cout<<"Palindrom"<<endl;
else
cout<<" Sorry not Palindrom"<<endl;
}
else{
int lLeft = iNumber/Calculate(lNumberOfdigit+1);
int lRight =iNumber%Calculate(lNumberOfdigit);
if(lLeft == reverse(lRight))
cout<<"Palindrom"<<endl;
else
cout<<" Sorry not Palindrom"<<endl;
}
}
int main(){
cout<<"hello"<>x;
}
Mohanabalan said on January 30, 2013
package palindrome;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import javax.print.DocFlavor;
public class Palindrome {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter the string or number to be checked”);
String check = br.readLine();
for(String part : check.split(” “)){
String rev;
rev = new StringBuffer(part).reverse().toString();
if(rev.equals(check)) {
System.out.println(“Equal”);
}
else {
System.out.println(“Not equal”);
}
}
}
}
Mohanabalan said on January 30, 2013
sorry the above code will not work for all cases this code will work
package palindrome;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import javax.print.DocFlavor;
public class Palindrome {
public static void main(String[] args) throws IOException {
List list = new ArrayList();
List list1 = new ArrayList();
//String a;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Enter the string or number to be checked”);
String check = br.readLine();
list1.add(check);
int i=0;
for(String part : check.split(” “)){
String rev;
rev = new StringBuffer(part).reverse().toString();
System.out.println(” “);
list.add(rev);
list.add(” “);
}
if(list.containsAll(list1)) {
System.out.println(“Equal”);
}
else {
System.out.println(“Not equal”);
}
}
}
Partha Pratim Sirker said on February 10, 2013
1. For even numbers make two halves lefthalf and righthalf
2. reverse left half reverseleft
3. if reverseleftright half answer is lefthalf+reverse of(left half)
for odd the above strategy will hold with only exception that middle digit will be included in both left and right half
And during answer also the middle digit will be merged
See complete java code here
[http://www.dsalgo.com/2013/02/NextPalindrome.php.html][1]
[1]: http://www.dsalgo.com/2013/02/NextPalindrome.php.html
Kahn said on February 24, 2013
here’s mine.it alway only need reverse half part of a number.
bool isPalindrome(int num)
{
assert(num>=0);
int i = 0,n;
while(1)
{
i = i*10 + num%10;
n = num;
num = num/10;
if(i == num)
{
return true;
break;
}
else if(i > num)
{
if(i == n)
return true;
else return false;
break;
}
if(i == 0)
{
return false;
break;
}
}
}
Sanket Korgaonkar said on March 2, 2013
/****************************************************
*
* Method :: intPalin
*
* Description :: Returns true, if integer passed in
* is a palindrome, false if otherwise
*
*****************************************************/
bool intPalin2( int a )
{
int noOfPlaces = 1;
int temp = a;
/*———————————————–
If number is negative return false.
————————————————*/
if( a 10 )
{
noOfPlaces++;
temp = (int)( temp/10 );
}
/*———————————————–
Chop off left and right ends of the number and
compare.
————————————————*/
int i = 1;
temp = a;
while( temp > 0 )
{
int div = (int) pow( 10, ( noOfPlaces – i ) );
int start = (int ) temp/div;
int end = temp % 10;
if( start != end )
return false;
else
{
temp = ( temp % div ) – ( temp % 10 );
temp = (int) temp/10;
i = i + 2;
/* cout << "\n Debug op :: " << temp; */
}
}
return true;
};
A Fluter said on March 3, 2013
When I first came out the revert number solution, it passed all the test cases.
For those test case that overflows if reverted, that means the reverted number is not the same as the original input number, which returns false, which is the right answer, looks tricky…
Sheikh Ashiqul Islam said on March 7, 2013
I couldn’t figure it out how these two lines function. Can anyone please explain.
x = (x % div) / 10;
div /= 100;
NullPointer said on March 9, 2013
Your solution doesn’t work for java, the following is for java, and avoid overflow issue:
NullPointer said on March 9, 2013
The assumption is positive number.
NullPointer said on March 9, 2013
there is a small error:
while (v > 10)
should be:
while (v >= 10)
So the right solution for positive numbers:
I have tested with the only judge and it works for all positive numbers.
NullPointer said on March 9, 2013
Sorry wrong again.
Correct one:
chaosshui said on April 9, 2013
class Solution {
public:
bool isPalindrome(int x) {
if(x0){
res = 10*res + (num%10);
num = num/10;
}
return (res==x);
}
};
Eric, YU said on April 10, 2013
mydas said on April 14, 2013
BOOL isPalindromeNumber(int n)
{
if( n > 0 && n <= 9) return YES;
if(n 9)
{
newValue = newValue * 10 + n % 10;
n = n / 10;
t = n / 10;
}
newValue = (newValue * 10 + n % 10) * 10 + t;
return oldValue == newValue;
}
mydas said on April 14, 2013
Nikhil said on April 21, 2013
neoestod said on June 12, 2013
The recursion solution is pretty cool.
Z.Y.-Lu said on June 13, 2013
Here is one solution I came up with by Mathematica: