Coding Exercise – Palindrome Number – C++ – Online Judge

A Palindrome string is a string that mirrors itself, for example, ’12a21′ reverse is the same string and ‘abcde’ is not.  A Palindrome number is a integer number that has the same characteristics. Given an integer, check whether it is a palindrome integer.

It is easy to find out that the negatives cannot be palindromes. And we can convert the integer to string first. Then use two indices pointing to the first and last digit respectively. Return false it each comparison is not equal until the index pointers meet in the middle.

However, if no additional space is allowed (not strictly, because defining a loop variable is also called as additional space), we don’t need strings, arrays… Just to reverse an integer to check its reverse is the same.

But, please note, an integer is 32-bit and the reverse may overflow, for example, 1000000003 reverse will flow. Therefore, we can use a bigger type (e.g. long long in C++) to hold such numbers.

The problem is from http://oj.leetcode.com/problems/palindrome-number/

The following uses O(1) space complexity and the algorithm has O(n) complexity.

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

class Solution {
public:
    bool isPalindrome(int x) {
        // negative numbers are not parlindrome
        if (x < 0) return false;         
        // save the original value into a bigger type         
        unsigned long long a = x;         
        // reverse value stored here         
        unsigned long long r = 0;         
        while (x > 0) {
            r *= 10;
            r += (x % 10);
            x /= 10;
        }
        // if reverse = original then yes
        return (r == a);
    }
};

class Solution {
public:
    bool isPalindrome(int x) {
        // negative numbers are not parlindrome
        if (x < 0) return false;         
        // save the original value into a bigger type         
        unsigned long long a = x;         
        // reverse value stored here         
        unsigned long long r = 0;         
        while (x > 0) {
            r *= 10;
            r += (x % 10);
            x /= 10;
        }
        // if reverse = original then yes
        return (r == a);
    }
};

–EOF (The Ultimate Computing & Technology Blog) —