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:

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.

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.

VN:F [1.9.22_1171]
Rating: 4.7/5 (92 votes cast)
Palindrome Number, 4.7 out of 5 based on 92 ratings

137 responses to Palindrome Number

  1. Above code uses Stack memory
    ps: -ve case are not handled

    VN:F [1.9.22_1171]
    +12
    • Pretty cool way of utilizing recursion, and this works too.

      By the way this conditional:

      could be replaced by:

      VN:F [1.9.22_1171]
      0
    • 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 ?

      VN:F [1.9.22_1171]
      0
      • 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.

        VA:F [1.9.22_1171]
        +5
    • public static void main(String[] args){
      int x = 123421;
      if (x < 0){
      System.out.println("no." + x + " is not a Palindrome");
      return;
      }
      if(x = 10 ){
      temp = temp*10 + remain%10;
      //System.out.println(temp);
      remain /= 10;
      }
      temp = temp*10 + remain;
      if(temp == x){
      System.out.println(“yes, ” + x + ” is a Palindrome”);
      }

      VA:F [1.9.22_1171]
      0
    • I just want to ask isnt the recursive solution is doing rdundant work,its comparing same pair for twice??

      VN:F [1.9.22_1171]
      0
  2. 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;

    VA:F [1.9.22_1171]
    -1
    • 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;

      VA:F [1.9.22_1171]
      0
    • Consider the binary representation of 17 –> “10001″. Its binary representation is a palindrome, but 17 itself as a number is not.

      VN:F [1.9.22_1171]
      0
  3. 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;

    }

    VA:F [1.9.22_1171]
    +1
    • 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;
      }

      VA:F [1.9.22_1171]
      -1
  4. bool checkPalindrome(int a)
    {
    int x = a;
    int y = 0 ;
    for(;a;a=a/10)
    {
    y = y*10 + a%10;
    }
    return (x==y);
    }

    VN:F [1.9.22_1171]
    0
  5. 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;
    }

    VN:F [1.9.22_1171]
    0
    • oops.. another friend above has posted the same solution.. I’m sorry

      VN:F [1.9.22_1171]
      0
      • 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));

        VN:F [1.9.22_1171]
        0
        • hi, your code has faults,you are assigning 10 to x instead of comparing it to 10 and div seems to be not declared.

          VN:F [1.9.22_1171]
          0
  6. 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

    VN:F [1.9.22_1171]
    -1
  7. cant we use x/div!=1 instead of x/div>=10 in first alternative solution….

    VA:F [1.9.22_1171]
    0
  8. 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;

    }

    VN:F [1.9.22_1171]
    +1
  9. 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;

    VN:F [1.9.22_1171]
    -1
  10. 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;
    }
    }

    }

    VA:F [1.9.22_1171]
    -1
  11. 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)

    VN:F [1.9.22_1171]
    0
    • 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)

      VN:F [1.9.22_1171]
      0
  12. I have no clue why the code isn’t pasting correctly.

    VN:F [1.9.22_1171]
    0
  13. Admin,

    The below link does not work. can you please take a look?

    http://www.leetcode.com/category/amazon-interview

    VA:F [1.9.22_1171]
    0
  14. 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:

    VA:F [1.9.22_1171]
    -1
  15. Sorry, the code didn’t paste correctly. Here we go again:

    VA:F [1.9.22_1171]
    0
  16. 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”.

    VN:F [1.9.22_1171]
    -2
  17. 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;
    }

    VA:F [1.9.22_1171]
    0
  18. Here’s my solution. It uses the similar idea which hwl proposed but seems he didn’t give the exact code:

    VA:F [1.9.22_1171]
    +5
    • I think this is the best solution for now.

      VA:F [1.9.22_1171]
      0
      • This is not the best or different solution.

        Above code is same as reversing the integer, which may cause overflow.

        VA:F [1.9.22_1171]
        0
    • the code failed when it is 131000. so my code is

      VA:F [1.9.22_1171]
      0
      • oops! my python code shows some error. here is the c code:

        VA:F [1.9.22_1171]
        0
        • display still wrong with . so I post again:
          bool isPalindrome(int x) {
          if(x b) {
          b = b * 10 + a % 10;
          if(b==0) return false;
          a /= 10;
          }
          return (a == b) || a == (b / 10);
          }

          VA:F [1.9.22_1171]
          0
          • I don’t know why it display wrong. here is my code:
            bool isPalindrom(int x)
            {
            if (xb) {
            b = b*10 + a%10;
            if (b==0) return false; //the last bit is 0, is not palindrome
            a /=10;
            }
            return (a==b) || (a==b/10);
            }

            VA:F [1.9.22_1171]
            0
  19. 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;

    VA:F [1.9.22_1171]
    0
  20. Thanks. Try whether Linked list is palindrome?

    VA:F [1.9.22_1171]
    0
    • VA:F [1.9.22_1171]
      0
  21. 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?

    VA:F [1.9.22_1171]
    0
  22. 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?

    VN:F [1.9.22_1171]
    0
  23. it took me 3 year to understand this piece of code , but hell yeah, finally its done :-D

    VN:F [1.9.22_1171]
    0
  24. how abt this code in java. it is non recursive

    VN:F [1.9.22_1171]
    0
  25. VN:F [1.9.22_1171]
    0
  26. 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;
    }
    }
    }
    };

    VN:F [1.9.22_1171]
    0
  27. VN:F [1.9.22_1171]
    0
  28. 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;

    }

    VA:F [1.9.22_1171]
    -1
  29. 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”);
    }

    }

    }
    }

    VN:F [1.9.22_1171]
    0
  30. 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”);

    }

    }
    }

    VN:F [1.9.22_1171]
    0
  31. 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

    VA:F [1.9.22_1171]
    0
  32. 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;
    }
    }
    }

    VN:F [1.9.22_1171]
    0
  33. /****************************************************
    *
    * 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;
    };

    VA:F [1.9.22_1171]
    0
  34. 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…

    VN:F [1.9.22_1171]
    0
  35. I couldn’t figure it out how these two lines function. Can anyone please explain.

    x = (x % div) / 10;
    div /= 100;

    VN:F [1.9.22_1171]
    0
  36. Your solution doesn’t work for java, the following is for java, and avoid overflow issue:

    VN:F [1.9.22_1171]
    0
    • The assumption is positive number.

      VN:F [1.9.22_1171]
      0
    • 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.

      VN:F [1.9.22_1171]
      0
  37. Sorry wrong again.

    Correct one:

    VN:F [1.9.22_1171]
    0
  38. class Solution {
    public:
    bool isPalindrome(int x) {
    if(x0){
    res = 10*res + (num%10);
    num = num/10;
    }

    return (res==x);
    }
    };

    VN:F [1.9.22_1171]
    0
  39. VN:F [1.9.22_1171]
    0
  40. 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;
    }

    VA:F [1.9.22_1171]
    0
  41. VA:F [1.9.22_1171]
    0
  42. VN:F [1.9.22_1171]
    0
  43. The recursion solution is pretty cool.

    VN:F [1.9.22_1171]
    0
  44. Here is one solution I came up with by Mathematica:

    VA:F [1.9.22_1171]
    0
  45. ZJ said on June 20, 2013

    bool isPalindromeNumber(int x)
    {
    if (x 0; digits++)
    m = m/10;

    for (i = 0; i < digits / 2 – 1; i++)
    {
    if ( (x/10^(digits – 1)) % 10 != ((x/10^i) % 10) )
    return false;
    }

    return true;
    }

    VN:F [1.9.22_1171]
    0
  46. ZJ said on June 21, 2013

    bool isPalindrome(int x) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (x 0; digits++)
    m = m/10;

    int y, z, i, j;
    for (i = 0; i < digits / 2; i++)
    {
    int u=1, v =1;
    for (j =0; j<i; j++)
    u = u*10;
    for (j = 0; j<digits – i -1; j++)
    v= v*10;

    y=(x/u)%10;
    z=(x/v)%10;

    if(y != z) return false;
    }

    return true;
    }

    VN:F [1.9.22_1171]
    0
  47. This fails if there is 0 in the digits : check for 4001004
    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;
    }

    VA:F [1.9.22_1171]
    0
  48. VN:F [1.9.22_1171]
    0
    • where is your ‘max’ come from? Even in Java you need to declare first. Do you miss some of your code?

      VN:F [1.9.22_1171]
      0
      • sorry. I just saw the comment. no idea why lack of code

        VA:F [1.9.22_1171]
        0
      • public boolean isPalindrome(int x) {
        if (x = 10) {
        max = max * 10;
        }
        while (max >= 10) {
        if (x / max != x % 10) {
        return false;
        }

        x = x – x / max * max;
        x = x / 10;
        max = max / 100;
        }
        return true;
        }

        VA:F [1.9.22_1171]
        0
      • hmm…. Cannot post the right code…

        VA:F [1.9.22_1171]
        0
  49. its working fine. thanks for sharing such cool code snippets. siva

    VA:F [1.9.22_1171]
    0
  50. Mine method is as below:


    bool isPalindrome(int x) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if (x < 0)
    {
    return false;
    }

    return x == reverse(x);

    }

    int reverse(int x)
    {
    int rem = x;
    int result = 0;

    while (rem != 0)
    {
    result = result * 10 + rem % 10;
    rem /= 10;
    }

    return result;
    }

    PS1: I think the overflow is not a problem, since the input x must be within the integer range, also if the expected result is true, the reversed x should be the same as the original x, which means it will also be within range. Otherwise if the original x is within range and the reversed x gets out of the range, definitely they are not equal and anyway there is a false.
    PS2: What does the 'extra space' mean? Does it mean the stack space is allowed? In the suggested method there is code like 'int div = 1;' I think this will use 4 byte of stack space.
    Of course my method call a function and the function also need to allocate the stack space. So is there any definition of the 'extra space'?

    VN:F [1.9.22_1171]
    0
    • I also have doubt with your PS1 and agree with overflow is not a problm.
      Anyone can explain?3ks

      VA:F [1.9.22_1171]
      0
  51. public class Solution {
    public boolean isPalindrome(int x) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if( x =0 && x = y) {
    if(x == y) return true;
    y = y *10 + x%10;
    if(x == y) return true;
    x = x/10;
    }
    return false;
    }
    }

    VN:F [1.9.22_1171]
    0
  52. VN:F [1.9.22_1171]
    0
  53. VN:F [1.9.22_1171]
    0
  54. class Solution
    {
    public:

    inline int NumDigits(int x)
    {
    if (x < 10)
    {
    return 1;
    }
    return (int)(log10(x)+1.0);
    }

    inline int GetDigit(int x, int idx)
    {
    for (int i = 0; i < idx; i++)
    {
    x = x / 10;
    }
    int digit = x % 10;
    return digit;
    }

    bool isPalindrome(int x)
    {
    if (x < 0)
    {
    return false;
    }
    if (x < 10)
    {
    return true;
    }
    int len = NumDigits(x);
    for (int idx=0; idx < len / 2; idx++)
    {
    if (GetDigit(x, idx) != GetDigit(x, len-idx-1))
    {
    return false;
    }
    }
    return true;
    }
    };

    VN:F [1.9.22_1171]
    0
  55. VN:F [1.9.22_1171]
    0
    • VN:F [1.9.22_1171]
      0
  56. VN:F [1.9.22_1171]
    0
  57. static boolean isPalindromeNumber(int num){
    if (num 0){
    last = num % 10;
    first = num;
    i = 1;
    while (first > 9){
    first = first / 10;
    i = i*10 ;
    }
    if (last != first){
    return false;
    }
    num = (num – first*i – last)/10;
    }
    return true;
    }

    VN:F [1.9.22_1171]
    0
  58. static boolean isPalindromeNumber(int num){
    if ( num 0){
    last = num % 10;
    first = num;
    i = 1;
    while (first > 9){
    first = first / 10;
    i = i*10 ;
    }
    if (last != first){
    return false;
    }
    num = (num – first*i – last)/10;
    }
    return true;
    }

    VN:F [1.9.22_1171]
    0
  59. boolean isPalindromeNumber(int num){
    int last, first, i;
    if (num 0){
    last = num % 10;
    first = num;
    i = 1;
    while (first > 9){
    first = first / 10;
    i = i*10 ;
    }
    if (last != first){
    return false;
    }
    num = (num – first*i – last)/10;
    }
    return true;
    }

    VN:F [1.9.22_1171]
    0
  60. VN:F [1.9.22_1171]
    0
  61. static boolean isPalindromeNumber(int num){
    int last, first, i;

    //if (num 0){

    last = num % 10;
    first = num;
    i = 1;

    while (first > 9){
    first = first / 10;
    i = i*10 ;
    }

    if (last != first){
    return false;
    }

    num = (num – first*i – last)/10;
    }

    return true;
    }

    VN:F [1.9.22_1171]
    0
    • Help why I could not show the two lines:

      if (num 0){

      VN:F [1.9.22_1171]
      0
      • static boolean isPalindromeNumber(int num){
        int last, first, i;

        while (num > 0){
        last = num % 10;
        first = num;
        i = 1;
        while (first > 9){
        first = first / 10;
        i = i*10 ;
        }
        if (last != first){
        return false;
        }
        num = (num – first*i – last)/10;
        }
        return true;
        }

        VN:F [1.9.22_1171]
        0
        • and add one line between “int last,first, i;” and “while(num>0)”, if (num<0) return false;

          VN:F [1.9.22_1171]
          0
  62. Here is a bug: if I use “if (num 0){}”, the system will interpreter the two lines as “if (num 0)”
    I try to use “assert” to resolve this problem.

    VN:F [1.9.22_1171]
    0
    • obviously, “assert” does’t work!

      VN:F [1.9.22_1171]
      0
      • static boolean isPalindromeNumber(int num){
        int last, first, i;
        if (num = 0);
        while (num > 0){
        last = num % 10;
        first = num;
        i = 1;
        while (first > 9){
        first = first / 10;
        i = i*10 ;
        }
        if (last != first){
        return false;
        }
        num = (num – first*i – last)/10;
        }
        return true;
        }
        }

        VN:F [1.9.22_1171]
        0
        • static boolean isPalindromeNumber(int num){
          int last, first, i;
          if (num 9){
          first = first / 10;
          i = i*10 ;
          }
          if (last != first){
          return false;
          }
          num = (num – first*i)/10;
          }
          return true;
          }
          }

          VN:F [1.9.22_1171]
          0
          • static boolean isPalindromeNumber(int num){
            int last, first, i;
            if (num 9){
            first = first / 10;
            i = i*10 ;
            }
            if (last != first){
            return false;
            }
            num = (num – first*i)/10;
            }
            return true;
            }
            }

            VN:F [1.9.22_1171]
            0
          • static boolean isPalindromeNumber(int num){
            if (num 9){
            first = first / 10;
            i = i*10 ;
            }
            if (last != first){
            return false;
            }
            num = (num – first*i)/10;
            }
            return true;
            }

            VN:F [1.9.22_1171]
            0
  63. I am VERY SORRY for the mass dump comments! I am a newbie, and do not know how to del them.
    It seems that here is a bug when to use ” if (num 0){} or while(num !=0){}” in Java. I tried to use “assert” to resolve this problem, while I failed.

    Someone can HELP me?! Many Thanks!

    VN:F [1.9.22_1171]
    0
  64. I see! the bug is caused by “\”!

    VN:F [1.9.22_1171]
    0
  65. static boolean isPalindromeNumber(int num){
    int last, first, i;
    if (num >= 0) {
    while (num !=0){
    last = num % 10;
    first = num;
    i = 1;
    while (first > 9){
    first = first / 10;
    i = i*10 ;
    }
    if (last != first){
    return false;
    }
    num = (num – first*i)/10;
    }
    return true;
    }
    else {
    return false;
    }
    }

    VN:F [1.9.22_1171]
    0
    • This is rightly displayed! Avoid to use “>” and “<" in a reverse sequence in your codes!

      VN:F [1.9.22_1171]
      0
  66. VA:F [1.9.22_1171]
    0
  67. public boolean isPalindromeNo(int a){
    if(a == reverseNo(a)){
    System.out.println(“no is palindrome”);
    return true;
    }else{
    System.out.println(“no is not palindrome”);
    return false;
    }
    }
    public int reverseNo(int x){
    int r=0;
    while(x!=0){
    r = r*10 + x%10;
    x=x/10;
    }
    return r;
    }

    VA:F [1.9.22_1171]
    -1
  68. without extra variable

    VN:F [1.9.22_1171]
    -1
  69. #!/usr/bin/env python

    def shift(n):
    d = 1
    while n/d >= 10:
    d *= 10
    return n/d, n%10, (n%d)/10

    def is_palindrome(n):
    if n < 0:
    return False
    if n < 10:
    return True
    l, r, n = shift(n)
    return l == r and is_palindrome(n)

    VA:F [1.9.22_1171]
    0
  70. #include
    void main()
    {
    int x,int m=x;
    while(x!=0)
    {
    d=x%10;
    r=r*10+d;
    x=x/10;
    }
    if(m==r)
    {
    printf(“number is palindrome”);
    else
    printf(“number is not palindrome”);
    }
    }

    VN:F [1.9.22_1171]
    0
  71. while(num>0){
    int r=num%10;
    int result=result*10+r;
    num=num/10;
    }
    if(result==num)
    return true;
    else return false;

    VN:F [1.9.22_1171]
    0
  72. Thanks for the post. I have also written the program to find whether the number is palindrome or not using function. please have a look.
    http://ioeengineer.blogspot.com/2014/03/to-find-whether-number-is-palindrome-or.html

    VA:F [1.9.22_1171]
    0
  73. It’s probably nicer to wrap functionalities in separate functions like:

    {
    start = 0;
    int end = getNumberOfDigits;

    while(end>start)
    {
    if( getDigit(number, end) != getDigit(number, start))
    return false;
    }

    return true;
    }

    VA:F [1.9.22_1171]
    0
  74. VN:F [1.9.22_1171]
    0
  75. VA:F [1.9.22_1171]
    0
  76. VA:F [1.9.22_1171]
    +1
  77. The requirement “no extra space” is too strict.
    The first solution used an extra space for variable “div”, which is O(1) space.

    VA:F [1.9.22_1171]
    0
  78. #include
    #include
    using namespace std;
    int main()
    {
    unsigned long long int num,temp=0,i=0;
    cin>>num;
    i=num;
    if(num<0)
    cout<<"-1";
    else
    while(num)
    {
    temp=temp*10+num%10;
    num/=10;
    }
    cout<<temp<<endl;
    if(i==temp)
    {
    cout<<"is palindrome";
    }
    else
    {
    cout<<"not palindrome";
    }
    return 0;

    }

    VA:F [1.9.22_1171]
    0
  79. #!/usr/bin/python

    import sys

    x = raw_input(“Enter a number: “)
    try:
    x = int(x)
    except e:
    print (“Invalid number! Quitting”)
    sys.exit(0)

    while (x > 10):
    last_d = x %10
    print “last digit:” + str(last_d)
    x_cpy = x
    num_d = 0
    while (x_cpy > 10):
    num_d = num_d + 1
    x_cpy = x_cpy / 10
    first_d = x_cpy
    print “first digit:” + str(first_d) + “—\n”

    print “Num_d ” +str(num_d)
    x = x -(first_d * (10**num_d))
    print x
    x /= 10
    print “New number:” + str(x)

    if (first_d != last_d):
    print “Not a pallindrome! Exiting”
    sys.exit(0)

    print “It’s a pallindrome!”

    VN:F [1.9.22_1171]
    0
  80. it seems that nobody mentions the method below, check palindrome while reversing the number

    VA:F [1.9.22_1171]
    0
    • need terminate the loop early otherwise ‘a’ may overflow. but the program passes OJ.

      VA:F [1.9.22_1171]
      0
  81. bool isPalindromeNumber(unsigned int ip){
    unsigned int input = ip;
    unsigned int iter = 0;
    unsigned int Lsb = 0;
    while(input!=0)
    {
    iter *= 10;
    Lsb = input%10;
    iter += Lsb;
    input /= 10;
    }
    return ((iter-ip)==0);
    }

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.