LeetCode Palindrome Number: No Extra Space

Overview

LeetCode Palindrome Number could be solved by a more generic solution to cut off the head and tail digits and then compare them, other methods are given too.

LeetCode Palindrome Number Problem

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution without Extra Array

The description is quite fuzzy. The correct solution is every time we just get the first digit and the last digit in the given number to check whether it is equal, and then we cut them off, and keep the same comparing until the number reaches zero. The following C++ code is accepted by LeetCode OJ to pass this Palindrome Number problem:

bool isPalindrome(int x) {
        if(x < 0)             return false;         int n = 1;         while(x / n >= 10)
            n *= 10;

        while(n > 1) {
            if( (x % 10) !=
                (x / n) )
                return false;

            x = (x % n) / 10;
            n /= 100;
        }

        return true;
    }

Several more clarification by myself:

  1. `Extra space` just means we cannot store each digit individually like converting into string or use array to store every digits in that number, but we still can use variables. like use a variable to store the number of digits of that number.
  2. “Reverse Integer” does not work here because of the Overflow issue
  3. It is possible to do it in a recursive way by using stack memory.

Update: the following Java version including both recursive and iterative implementation can be accepted by LeetCode OJ as well to pass this Palindrome Number problem:

public class Solution {

    public boolean isPalindrome(int x) {
        if (Math.random() < 0.5) {
	    return isPalindrome1(x);
        }
	else {
	    return isPalindrome2(x);
	}
    }

    private boolean isPalindrome2(int x) {
	if (x < 0) {             return false;         } 	int d = (int) Math.pow(                         10,                          (int) Math.log10(x)); 	int a, b;  	while (d >= 10) {
            a = x / d;
	    b = x % 10;

   	    if (a != b) {
                return false;
            }

	    x = x % d / 10;
   	    d /= 100;
	}
	return true;
    }

    private boolean isPalindrome1(int x) {
	if (x < 0) {
            return false;
        }

	int d = (int) Math.pow(
                      10,
                      (int) Math.log10(x));

        return isPalindrome11(x, d);
    }

    private boolean isPalindrome11(int x, int d) {
	if (d < 10) {
	    return true;
	}

	int a = x / d, b = x % 10;

        if (a == b) {
	    return isPalindrome11(
                      x % d / 10,
                      d / 100);
        }
	else {
   	    return false;
	}
}

but note the recursive method does not meet the requirement of not using extra memory, because it uses extra stack memory which is not O(1). And also take a look at another similar interesting problem to apply palindrome in linked list: LeetCode Palindrome Linked List: O(1) Space 

Summary

LeetCode Palindrome Number could be solved by a more generic solution to cut off the head and tail digits and then compare them, other methods are given too.

Written on April 21, 2013