Reference: LeetCode EPI 4.9
Difficulty: Easy

My Post: Four Solutions All In One (Why overflow is a problem?)

Problem

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Note:

Example: 

1
2
Input:  121,  0,    100,   -120
Output: true, true, false, false

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

Hint: Beware of overflow when you reverse the integer.

Analysis

Methods:

  1. Brute-Force
    • Convert the number to a string.
    • Time: $O(N)$, where $N$ is the number of characters. 8 ms
    • Space: $O(N)$, since we create a string.
  2. ReverseAndCompare
    • Reverse a number and compare it to the initial one.
    • Note: Be aware of overflow problem.
    • Time: $O(N)$ 6 ms
    • Space: $O(1)$
  3. Reverse Half
    • Similar idea to ReverseAndCompare, but it only reverts half of the int number. If the reverse of the last half of the palindrome should be the same as the first half.
      • E.g. 1221 from 21 to 12.
    • Time: $O(N) = O(\log_{10}{n})$ 7 ms
    • Space: $O(1)$
  4. CompareOneByOne EPI 4.9
    • Calculate the most significant digit msd and the least significant digit lsd and compare.
    • numDigit = (int) Math.floor(Math.log10(x)) + 1
    • Time: $O(N)$ 8 ms
    • Space: $O(1)$

Code

Test Case:

1
2
3
4
5
6
Input:  121,  0,    100,   -120
Output: true, true, false, false

Overflow test case:
2147483647 // This is the max value of 32-bit integer.
2147447412 // A good test.

Brute-Force

Note:

  • The condition could be written as:
    • if (x <= 0) return x == 0
    • Since the code can handle $0$ case, it is fine.
  • Be careful of the corner case n / 2
  • When getting the size of a String, remember to use str.length() rather than str.length.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// convert to string
public boolean bruteForce(int x) {
  if (x < 0) { // negative number
    return false;
  }
  String str = String.valueOf(x);
  int n = str.length();
  for (int i = 0; i < n / 2; ++i) { // right-leaning
    if (str.charAt(i) != str.charAt(n - i - 1)) {
      return false;
    }
  }
  return true;
}

ReverseAndCompare

Note:

  • Be aware of potential overflow problems.
  • It’s doomed when the reversed number of $x$ overflows. Marked
    • But it seems okay because I can’t input number larger than 2147483647.
    • Also, if x is 2147483647, the reversed number is 7463847412 which is actually a negative number that could not be equal to $x$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// reverseAndCompare
public boolean reverseAndCompare(int x) {
  if (x < 0) { // negative number
    return false;
  }
  return (x == reverse(x)); // x is converted to long type
}

private long reverse(long x) {
  long sum = 0;
  while (x != 0) {
    sum = sum * 10 + x % 10;
    x /= 10;
  }
  return sum;
}

Reverse Half

Note:

  • Careful of the corner case. Test it out for x = 0 and x = 100. Unlike other solutions, this one requires special check for those numbers.
  • In the return statement, there are different cases for even or odd numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// revert half
public boolean revertHalf(int x) {
  if (x < 0 || (x != 0 && x % 10 == 0)) {
    return false;
  }
  
  int revertedNum = 0;
  while (x > revertedNum) {
    // e.g. 12321. 
    // revertedNum = 1,    12,   123 // stop here
    //           x = 1232, 123,  12
    revertedNum = revertedNum * 10 + x % 10;
    x /= 10;
  } // x = 12, revertedNum = 123
  return x == revertedNum || x == revertedNum / 10; // even or odd
}

CompareOneByOne

Note:

  • Learn how to calculate the number of digits.
  • Use msdMask to get the most significant digit.
  • Can use while or for, but for turns out to be clearer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// compareOneByOne
public boolean compareOneByOne(int x) {
  if (x < 0) {
    return false;
  }
  int numDigit = (int) Math.floor(Math.log10(x)) + 1;
  int msdMask = (int) Math.pow(10, numDigit - 1); // e.g. 123: 100
  for (int i = 0; i < numDigit / 2; ++i) { // or while (x != 0) {
    int lsd = x % 10;
    int msd = x / msdMask; // e.g. 321 / 100 = 3
    if (lsd != msd) {
      return false;
    }
    // set for next
    x %= msdMask; // e.g. 321 % 100 = 21
    x /= 10; // e.g. 21 / 10 = 2
    msdMask /= 100; // 1234, mask 1000 => next: 23, mask = 10
  }
  return true;
}