My solution by calculating the reversed integer. Time complexity is O(lgx).


  • 2
    S

    The basic idea is calculate the reversed integer by repeating computing the reminder and quotient.
    The time complexity is O(lgx).

    public boolean isPalindrome(int x) {
    	if(x < 0) {
    		return false;
    	}else {
    		int reversed = 0;
    		int reminder, quotient = x;
    		do {
    			reminder = quotient % 10;
    			quotient = quotient / 10;
    			reversed = reversed * 10 + reminder;
    		}while(quotient != 0);
            return reversed == x;
    	}
    }

  • 1
    S

    Although this code gets accepted, it seems that it does not handle the case when the reverse of x exceeds Integer.MAX_VALUE? Maybe you want to add in this part.


  • 0
    S

    Yes, you are right. I did ignore the case when the reverse of x exceeds Integer.MAX_VALUE. Inorder to handle this case, the variable reversed has to be declared as long integer type.


  • 0
    Y

    Actually you don't need to modify your code, although reversed number may overflow, but it doesn't affect the result of judging whether it is a palindrome. For any palindrome integer number, e.g. 123454321, its reversed number never overflow. For non-palindrome number e.g. 1023456789, the reversed number 9876543201 overflow to a negative number, but that doesn't matter since reversed!=x yields a false return.


  • 7
    N

    We can also divide only till half of the number.
    Think that help to solve overflowing:

    public boolean isPalindrome(int x) {
            if (x < 0) {
                return false;
            }
    
            int slow = x;
            int fast = x;
            int half = 0;
    
            while (fast / 100 > 0) {
                half = 10 * half + slow % 10;
                fast /= 100;
                slow /= 10;
            }
    
            if (fast < 10) {
                return (((slow / 10) ^ half) == 0);
            } else {
                return (((slow / 10) ^ (10 * half + slow % 10 )) == 0);
            }
        }

  • 0
    E

    same with mine.

     int reverseNum(int x){
    	int y=0;
    	while(x>0){
    		y=10*y+x%10;
    		x/=10;
    	}
    	return y;
    }
    
      bool isPalindrome(int x) {
            if(x<0)return false;
            return x==reverseNum(x);
        }

  • 0
    E

    you are right.


  • 0
    L

    My idea, we only need to consider the left half and right half of the value, and if we reverse the right half, the palindrome integer's left half and reversed right half must be equal.
    Notice: This algorithm can't handle the condition when the end of integer is 0. so check it at first.

    public class Solution {
        public boolean isPalindrome(int x)
        {
            if (x != 0 && x % 10 == 0)
            {
                return false;
            }
            
            int right = 0;
            while (x > right)
            {
                right *= 10;
                right += x % 10;
                // For odd digits value such as 919
                if (right == x)
                {
                    return true;
                }
                x = x / 10;
            }
            
            // For even digits value such as 10001.
            return x == right;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.