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