Problem

Determine whether an integer is a palindrome.

Follow up

Do this without extra space.

Definition

Palindrome Definition

Examples

Example 1:

1
2
3
4
5

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

Example 2:

1
2
3
4
5

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:

1
2
3
4
5

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

Solution

Method 1 - Using % and Multiplication by 10

Problems related with numbers are frequently solved by / and %. No need of extra space is required. This problem is similar with the Reverse Integer problem.

  • Modding (%) the input int by 10 will extract off the rightmost digit. example: (1234 % 10) = 4
  • Multiplying an integer by 10 will “push it left” exposing a zero to the right of that number, example: (5 X 10) = 50
  • Dividing an integer by 10 will remove the rightmost digit. (75 / 10) = 7

Note: no extra space here means do not convert the integer to string, since string will be a copy of the integer and take extra space. The space take by div, left, and right can be ignored.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public boolean isPalindrome(int x) {
	//negative numbers are not palindrome
	if (x<0) {
		return false;
	}
	
	// initialize how many zeros
	int div = 1;
	while (x / div >= 10) {
		div *= 10;
	}

	while (x != 0) {
		int left = x / div;
		int right = x % 10;

		if (left != right) {
			return false;
		}
			
		x = (x % div) / 10;
		div /= 100;
	}

	return true;
}

Method 2 - Reverse the number and check if equal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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

	return x == reverse(x);
}

private int reverse(int x) {
	long reversed = 0, xLong = x;
	while (xLong != 0) {
		long lastDigit = xLong % 10;
		reversed = reversed * 10 + lastDigit;
		xLong = xLong / 10;
	}            
	if (reversed > Integer.MAX_VALUE || reversed < Integer.MIN_VALUE) {
		reversed = 0;
	}
	return (int)reversed;        
}

Method 3 - Convert to string

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public boolean isPalindrome(int x) {
	if (x < 0) {
		return false;
	}
	String xStr = Integer.toString(x);
	for (int i = 0; i < xStr.length() / 2; i++) {
		if (xStr.charAt(i) != xStr.charAt(old.length() - i - 1)) {
			return false;
		}
	}
	return true;
}