Labels

Saturday, March 14, 2015

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

No comments:

Post a Comment