Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Naive Way: At first, I try to use division(/) to get highest digit and mod(%) to get lowest digit and eliminate both digit once manipulated, but fail at case 10021. And then, I turn to a more brute force way. Write a sub function that get a particular digit from candidate integer. Keep compare mirror digits.

 public class Solution {  
   static final int MAX_DIGIT = 10;  
   public boolean isPalindrome(int x) {  
     // negative integer is not palindrome  
     if(x < 0) return false;  
     int low = 0, high = MAX_DIGIT;  
     // get highest digit  
     while(x < Math.pow(10,high)) high--;  
     // validate each digit pair  
     while(low < high) if(getDigit(low++, x)!=getDigit(high--, x)) return false;  
     return true;  
   }  
   private int getDigit(int n, int x){  
     // edge case, x doesn't have n digit  
     if(Math.pow(10, n) > x) return -1;  
     // edge case, n == base  
     if(n==(int)Math.pow(10,MAX_DIGIT) && x >= n) return x/n;  
     // general case  
     return (x%(int)Math.pow(10,n+1) - x%(int)Math.pow(10,n))/(int)Math.pow(10,n);  
   }  
 }  

After viewing some solution in Discuss, I found that there are some one who handles 10021 case in a correct way. I developed my own based on previous attempt.

 public class Solution {  
   static final int base = 1000000000;  
   public boolean isPalindrome(int x) {  
     // negative integer is not palindrome  
     if(x < 0) return false;  
     int i = base;  
     while(i > x) i/= 10;  
     while(i > 1){  
       if(x/i != x%10) return false;  
       x -= x/i * i;  
       x /= 10;  
       i /= 100;  
     }  
     return true;  
   }  
 }  

Improved Way: I didn't think of reverse the integer and than compare. And I think reverse an integer may incur a lot more edge case. But if you are able to deal with edge case gracefully, that's a good method. See o-1-space-o-lgn-time-java-solution-no-overflow-risk

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321 

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Naive Way:  My method is to keep getting the least valuable digit from x. This method is a good approach when I implements it. But the edge case really bothers me. I manually add edge overflow cases in three parts, which is pretty bad.

 public class Solution {  
   public int reverse(int x) {  
     // edge case  
     if(x==Integer.MIN_VALUE) return 0;  
     // negative number, convert from positive  
     if(x < 0) return -reverse(-x);  
       
     int y = 0;  
     for(int i = 10;x!=0;i *= 10){  
         
       // overflow  
       if(y > Integer.MAX_VALUE/10) return 0;  
         
       y *= 10;  
       y += (x%i)/(i/10);  
       x -= x%i;  
         
       // overflow  
       if(i==1000000000 && x!=0){  
         if(y > Integer.MAX_VALUE/10) return 0;  
         y *= 10;  
         y += x/i;  
         x = 0;  
       }  
     }  
     return y;  
   }  
 }  

Improved Way: A better way is to include as many as edge case in the main loop. Then I try to get the most valuable digit first. It turns out that it's hard to deal with edge case also.

 public class Solution {  
   static final int base = 1000000000;  
   public int reverse(int x) {  
     // edge case, overflow  
     if(x == Integer.MIN_VALUE) return 0;  
     // negative value  
     if(x < 0) return -reverse(-x);  
       
     int y = 0, highest = 1;  
     for(int i = base;i != 0;i/= 10){  
       // note down highest digit  
       if(x >= i && highest==1) highest = i;  
         
       // edge case, overflow  
       if(x/i > 2 && highest == base && i==1) return 0;  
       if(y > Integer.MAX_VALUE - x/i*(highest/i)) return 0;  
         
       y += x/i*(highest/i);  
       x -= x/i*i;  
     }  
     return y;  
   }  
 }  

Using Double or Long can simply deal with overflow, just check the result after reverse. But I don't think that's what the question is asking.

And my first approach is a correct thinking, but not being correctly manipulated. Here is a gentle way to deal with overflow edge case.

 public class Solution {  
   public int reverse(int x) {  
     // edge case  
     if(x==Integer.MIN_VALUE) return 0;  
     // negative number, convert from positive  
     if(x < 0) return -reverse(-x);  
       
     int y = 0;  
     while(x != 0){  
         
       // edge case, overflow  
       if(y > Integer.MAX_VALUE/10) return 0;  
         
       y *= 10;  
       y += x%10;  
       x /= 10;  
     }  
     return y;  
   }  
 }