Palindrome Number

Problem

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

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.

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

Constraints

  1. don’t convert to string
  2. Negatives are automatically disqualified

Approach

  1. We can push all digits to an array and check start and end as we converge pointers
  2. To avoid using O(n) extra space, we can generate a reversed number of the original and compare

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isPalindrome(int x) {
      if (x < 0) return false;
      int reversed = 0;
      int temp = x;
      while (temp) {
        int digit = temp % 10;
        reversed = reversed*10 + digit;
        temp /= 10;
      }
      return (reversed == x);
    }
};

Test cases

  1. negative numbers
  2. 1234
  3. Large numbers to see if we get time out
  4. test 0 and other single digits