What's the meaning of no extra space? (JAVA)


  • 1
    S

    How about int i =1; or int y = x? Does it mean no variable declared, like

    public class Solution {
        	   public boolean isPalindrome(int x) {
        	        if(x<0) return false;
        	        if(x<10) return true;
        	       return x/(int)Math.pow(10, ((int) Math.log10(x)+2)/2)==back(x%(int)Math.pow(10, ((int) Math.log10(x)+1)/2),((int) Math.log10(x)-1)/2+1);
        	    }
        
        		private int back(int x,int y) {
        			if(y==1)return x;
        			return back(x/10,y-1)+(x%10)*(int)Math.pow(10, y-1);
        }
    }

  • -1
    I
    public boolean isPalindrome(int x) throws InterruptedException {
            	
    	if(x<0) {
    		return false;
    	}
    	
    	int i = 1;
    	int d = 0;
    	boolean overflowBreak = false;
    	// find num of digits
    	while(x/i != 0 && !overflowBreak) {
    		d++;
    		//System.out.println(x+"/"+i+" = "+x/i);
    		if(Integer.MAX_VALUE/i >= 10) {
    			i *= 10;
    		}
    		else
    		{
    			overflowBreak = true;
    			// if i is more than Integer.MAX_VALUE , then digits remained should not be more than 1.
    			if(x/i > 9) {
    				return false;
    			}
    		}
    		
    	}
    	//System.out.println("digits ="+d);
    	
    	int left = d-1;
    	int right = 0;
    	
    	
    	while(left > right) {
    		// check left with right
    		//System.out.println((x%(int)Math.pow(10, left+1))/(int)Math.pow(10, left) +" --> "+ (x%(int)Math.pow(10, right+1))/(int)Math.pow(10, right));
    		if((x%(int)Math.pow(10, left+1))/(int)Math.pow(10, left) == (x%(int)Math.pow(10, right+1))/(int)Math.pow(10, right)) {
    			left--;
    			right++;
    		}
    		else {
    			return false;
    		}
    	}
    	
    	return true;
    }
    

  • 0
    M

    Definitely not. It means use only constance space. You can do nearly nothing if no variables declared. Even you call built-in functions, they did declare variables.


  • 6
    W
    There is a way to not declare any variable, although complicated
        
    public class Solution {
            public boolean isPalindrome(int x) {
                if(x<0){
                    return false;
                }
                if(x>999999999){
                    if(x%10 != x/1000000000){
                        return false;
                    }
                    x = x%1000000000;
                    x = x/10;
                    if(x%10 != x/10000000){
                        return false;
                    }
                    x = x%10000000;
                    x = x/10;
                    if(x%10 != x/100000){
                        return false;
                    }
                    x = x%100000;
                    x = x/10;
                    if(x%10 != x/1000){
                        return false;
                    }
                    x = x%1000;
                    x = x/10;
                    if(x%10 != x/10){
                        return false;
                    }
                    return true;
                }else if(x>99999999){
                    if(x%10 != x/100000000){
                        return false;
                    }
                    x = x%100000000;
                    x = x/10;
                    if(x%10 != x/1000000){
                        return false;
                    }
                    x = x%1000000;
                    x = x/10;
                    if(x%10 != x/10000){
                        return false;
                    }
                    x = x%10000;
                    x = x/10;
                    if(x%10 != x/100){
                        return false;
                    }
                    return true;
                }else if(x>9999999){
                    if(x%10 != x/10000000){
                        return false;
                    }
                    x = x%10000000;
                    x = x/10;
                    if(x%10 != x/100000){
                        return false;
                    }
                    x = x%100000;
                    x = x/10;
                    if(x%10 != x/1000){
                        return false;
                    }
                    x = x%1000;
                    x = x/10;
                    if(x%10 != x/10){
                        return false;
                    }
                    return true;
                }else if(x>999999){
                    if(x%10 != x/1000000){
                        return false;
                    }
                    x = x%1000000;
                    x = x/10;
                    if(x%10 != x/10000){
                        return false;
                    }
                    x = x%10000;
                    x = x/10;
                    if(x%10 != x/100){
                        return false;
                    }
                    return true;
                }else if(x>99999){
                    if(x%10 != x/100000){
                        return false;
                    }
                    x = x%100000;
                    x = x/10;
                    if(x%10 != x/1000){
                        return false;
                    }
                    x = x%1000;
                    x = x/10;
                    if(x%10 != x/10){
                        return false;
                    }
                    return true;
                }else if(x>9999){
                    if(x%10 != x/10000){
                        return false;
                    }
                    x = x%10000;
                    x = x/10;
                    if(x%10 != x/100){
                        return false;
                    }
                    return true;
                }else if(x>999){
                    if(x%10 != x/1000){
                        return false;
                    }
                    x = x%1000;
                    x = x/10;
                    if(x%10 != x/10){
                        return false;
                    }
                    return true;
                }else if(x>99){
                    if(x%10 != x/100){
                        return false;
                    }
                    return true;
                }else if(x>9){
                    if(x%10 != x/10){
                        return false;
                    }
                    return true;
                }else{
                    return true;
                }
            }
        }

  • 0

    No extra variables, no recursion or any other function calls... that might be the first real no extra space solution I've seen. Bravo :-)

    A more compact one based on your idea:

    public boolean isPalindrome(int x) {
        if (x > 999999999) return (x/1000000000 - x/1) % 10 +
                                  (x/100000000 - x/10) % 10 +
                                  (x/10000000 - x/100) % 10 +
                                  (x/1000000 - x/1000) % 10 +
                                  (x/100000 - x/10000) % 10 == 0;
        if (x > 99999999) return (x/100000000 - x/1) % 10 +
                                 (x/10000000 - x/10) % 10 +
                                 (x/1000000 - x/100) % 10 +
                                 (x/100000 - x/1000) % 10 == 0;
        if (x > 9999999) return (x/10000000 - x/1) % 10 +
                                (x/1000000 - x/10) % 10 +
                                (x/100000 - x/100) % 10 +
                                (x/10000 - x/1000) % 10 == 0;
        if (x > 999999) return (x/1000000 - x/1) % 10 +
                               (x/100000 - x/10) % 10 +
                               (x/10000 - x/100) % 10 == 0;
        if (x > 99999) return (x/100000 - x/1) % 10 +
                              (x/10000 - x/10) % 10 +
                              (x/1000 - x/100) % 10 == 0;
        if (x > 9999) return (x/10000 - x/1) % 10 +
                             (x/1000 - x/10) % 10 == 0;
        if (x > 999) return (x/1000 - x/1) % 10 +
                            (x/100 - x/10) % 10 == 0;
        if (x > 99) return (x/100 - x/1) % 10 == 0;
        if (x > 9) return (x/10 - x/1) % 10 == 0;
        return x >= 0;
    }
    

Log in to reply
 

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