Question

Formatted question description: https://leetcode.ca/all/9.html

9. Palindrome Number

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

Example 1:

Input: 121
Output: true
Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.


Follow up:

Coud you solve it without converting the integer to a string?



Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer",
you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Algorithm

First judge whether x is a negative number. A small trick can be used here, because the highest bit of an integer cannot be 0, so the lowest bit of the palindrome cannot be 0, except for the number 0, so if you find that the end of a positive number is 0 , Just return false directly. Well, let’s look at the specific solution below.

To verify the number of palindromes, you need to see if the front and back half are symmetrical. If you flip the second half, you can see if it is equal to the first half. So the method is to take out the second half of the number and reverse it.

The specific method is to take the remainder of 10 each time, take the lowest digit, and then add it to the end of the taken number, which is to multiply revertNum by 10 and add the remainder , So the flip is completed at the same time, every time a lowest digit is taken, x must be divided by 10. In this way, the loop stops when revertNum is greater than or equal to x.

Since the number of palindromes can be even or odd,

  • if it is an even number, then revertNum should be equal to x;
  • if it is an odd number, then the middle number is at the lowest bit of revertNum, and it should be divided by 10 And x are equal

Code

Java

public class Palindrome_Number {

	public static void main(String[] args) {
		Palindrome_Number out = new Palindrome_Number();
		Solution s = out.new Solution();

		System.out.println(s.isPalindrome(12321));
		System.out.println(s.isPalindrome(Integer.MAX_VALUE));
	}

	public class Solution {
		public boolean isPalindrome(int x) {
			if(x < 0) {
				return false;
			}

			long rev = 0;

			int y = x;
			while(y > 0) {
				int remainder = y % 10;
				y /= 10;

				rev = rev * 10 + remainder;
			}

			if(rev > Integer.MAX_VALUE) {
				return false;
			}

			return ((int) rev) == x;
		}
	}

	public class Solution2 {
	    public boolean isPalindrome(int x) {
	        if (x < 0) {
	            return false;
	        }

	        int xorig = x;
	        int rev = 0;
	        while(x > 0) {
	            rev = rev * 10 + x % 10;
	            x /= 10;
	        }

	        return rev == xorig;
	    }
	}
}

All Problems

All Solutions