Question

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

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -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: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Follow up: Could you solve it without converting the integer to a string?

Algorithm

First, let’s check if x is a negative number. A small trick can be used here. Because the highest bit of an integer cannot be 0, the lowest bit of the palindrome cannot be 0 except for the number 0. So if the end of a positive number is 0, just return false directly.

To verify the number of palindromes, we need to check if the front and back half are symmetrical. If we flip the second half, we 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. This means we multiply revertNum by 10 and add the remainder. 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

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;
	    }
	}
}

############

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int y = 0, t = x;
        while (t != 0) {
            y = y * 10 + t % 10;
            t /= 10;
        }
        return x == y;
    }
}

// OJ: https://leetcode.com/problems/palindrome-number/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        long long a = x, b = 0;
        while (x) {
            b = b * 10 + x % 10;
            x /= 10;
        }
        return a == b;
    }
};

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        y, t = 0, x
        while t:
            y = y * 10 + t % 10
            t //= 10
        return x == y

############

class Solution(object):
  # normal way
  def _isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    z = x
    y = 0
    while x > 0:
      y = y * 10 + x % 10
      x /= 10
    return z == y

  # faster way
  def isPalindrome(self, x):
    """
    :type x: int
    :rtype: bool
    """
    if x < 0 or (x != 0 and x % 10 == 0):
      return False
    half = 0
    while x > half:
      half = half * 10 + x % 10
      x /= 10
    return x == half or half / 10 == x

func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	result := 0
	y := x
	for y != 0 {
		result = result * 10 + y%10
		y /= 10
	}
	return result == x
}

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
    let str = x + '';
    let left = 0,
        right = str.length - 1;
    while (left < right) {
        if (str[left] != str[right]) return false;
        left++;
        right--;
    }
    return true;
};

impl Solution {
    pub fn is_palindrome(mut x: i32) -> bool {
        if x < 0 || (x % 10 == 0 && x != 0) {
            return false;
        }
        let mut y = 0;
        while x > y {
            y *= 10;
            y += x % 10;
            x /= 10;
        }
        x == y || x == y / 10
    }
}

function isPalindrome(x: number): boolean {
    if (x < 0 || (x > 0 && x % 10 === 0)) {
        return false;
    }
    let y = 0;
    for (; y < x; x = ~~(x / 10)) {
        y = y * 10 + (x % 10);
    }
    return x === y || x === ~~(y / 10);
}

9 - Palindrome Number

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions