If I use extra space, will OJ give me a notice or warning?


  • 0
    Z

    This is my code, It pass through the OJ test. But I am not sure about the restriction

    class Solution {
    public:
        bool isPalindrome(int x) {
            int reverse=0;
            int standard=x;
            if(x==0) return true;
            if (x<0) return false;
            while(x!=0){
                reverse=reverse*10+x%10;
                x=x/10;
            }
            if (standard==reverse) return true;
            else return false;
        }
    };

  • 0
    S

    Nope, as I tested it before. But for extra space is easy to check, it usually only defines a few variables in code.


  • 0
    Z

    Thank U for the answer! BTW, do u know what's the hints mean when it said:
    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.

    What is the generic way to solve this problem? Thanks!


  • 0
    P

    think xor. what are the properties of bit wise xor?


  • 0
    O

    Could you extend a little bit? I did not quite understand how do you take advantage of xor operator.


  • 0
    P

    please ignore xor. I don't know how it passed all of the 11500 test cases. i was thinking xoring all the digits. If it's a palindrome, the result should be 0 for even number of digits and the digit in the middle for odd number of digits. which is correct for palindromes but also the case for numbers like 1122 or 1119333. xor doesn't validate the location of each digit. below is how i solved it i guess more generically:

    public  boolean isPalindrome(int x) {
        if(x<0){
            return false;
        }
        int digitCount = 0;
        for(int m = x;m!=0;m/=10,digitCount++);
        for(int i = 0; i< digitCount/2;i++){
            if(getDigitAt(x,i) !=getDigitAt(x,digitCount-i-1)){
                return false;
            }
        }
        return true;
    }
    private  int getDigitAt(int num, int index){
        while(index-- >0){
            num/=10;
        }
        return num %10;
    }

  • 0
    P

    'reverse' would overflow if x=1999999999 and x is of 32 bit signed int


  • 0
    P

    I'm not sure what the definition of "no extra space" is. does it mean O(1) space regardless what the input is? if so, i would argue it's ok to use a string as mentioned in the problem since each int is bounded. The most you will probably need is a string of length 10 to hold 2147483647 (2^31-1)


  • 1
    J

    There is no variable in my code.

    class Solution {
        public:
            bool isPalindrome(int x) {
                if(x<0)
                    return false;
                while(x)
                {
                    if(x/int(pow(10,int(log10(x))))!=x%10)
                        return false;
                    if(int(log10(x)))
                    {
                        if(int(log10(x))-int(log10(x-(x/int(pow(10,int(log10(x)))))*pow(10,int(log10(x))))>1))
                            if((x%int(pow(10,int(log10(x))-int(log10(x-(x/int(pow(10,int(log10(x)))))*pow(10,int(log10(x))))))))>9)
                                return false;
                        x/=pow(10,int(log10(x))-int(log10(x-(x/int(pow(10,int(log10(x)))))*pow(10,int(log10(x))))));
                    }
                    x-=(x/int(pow(10,int(log10(x)))))*int(pow(10,int(log10(x))));
                }
                return true;
            }
        };

  • 0
    C

    There is no variable in my code. (Accept)

    class Solution {
        public:
        bool isPalindrome(int x) {
        		if(x<0)
        			return false;
        		while(x)
        		{
        			if(x/int(pow(10,int(log10(x))))!=x%10)
        				return false;
        			if(int(log10(x)))
        			{
        				
        				if((x/int(pow(10,int(log10(x))-1)))%10==0)
        				{
        					if(x/10%10!=0)
        						return false;
        					else
        					{
        						x+=10;
        						x-=(x/int(pow(10,int(log10(x))))-1)*int(pow(10,int(log10(x))));
        						x+=int(pow(10,int(log10(x))-1));
        					}
        				}
        				x/=10;
        			}
        			x-=(x/int(pow(10,int(log10(x)))))*int(pow(10,int(log10(x))));
        		}
        		return true;
        }};
    

  • 0
    Y

    Can not past when the integer is 10000021.


  • 0
    J

    thanks.
    I have fixed this bug.


  • 0
    D

    The extra space just don't show in the code ,but you use standard function,in these functions it will use space .


  • 0
    P

    If it overflows, it means it is not the same as the original x. This will give a false for the result. Am I right?


  • 0
    A

    I guess OJ doesn't really check extra space. Here's my solution:

    public boolean isPalindromeInPlace(int x)
    {
    	int len = 1;
    	long i = 10;
    	while (x/i !=0)
    	{
    		i *=10;
    		len++;
    	}
    	for (i = 0;i<len/2;i++)
    	{
    		int left = x/((int) Math.pow(10, (len-i*2-1)));
    		int right = x%10;
    		if (left != right)
    			return false;
    		x = x%((int)Math.pow(10, (len-i*2-1)));
    		x = x/10;
    	}
    	return true;
    }

  • 4
    D

    here is my code it is not using any extra space and any inbuilt functions

    bool isPalindrome(int x) {
        int n=1;//n stores value of highest power of 10 less than x like for 1221 n=1000
        if(x<0)
        return false; //since negative number cant be palindrome
        while(x/n>=10)
            n*=10; //calculating n
        while(x && n>1)
        {
            if(x/n!=x%10) //checking first and last number
            return false;
            x=x-(x/n)*n; //removing leftmost digit  from x
            x/=10; //removing rightmost digit from x
            n/=100;
        }
        return true;
    }
    

  • 0
    Z

    Is n using extra space?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.