Sqrt problem , my solution works perfectly but it gives error on leetcode.


  • 0
    C

    My solution below works perfectly , but leetcode gives error, i cant see the problem.
    Leetcode claims that there is runtime error with:
    Last executed input:
    2147395599

    public int MySqrt(int x) 
    	{
    		if (x == 0) { return 0; }
    		if (x >= 1 && x < 3) { return 1; }
    		if (x >= 3 && x < 9) { return 2; }
    		if (x >= 9 && x < 16) { return 3; }
    		if (x >= 16 && x < 25) { return 4; }
    		if (x >= 25 && x < 36) { return 5; }
    
    		int length = x / 5;
    		int[] candidates = new int[length + 1];
    
    		for (int i = 0; i < length + 1; i++) 
    		{
    			candidates [i] = i;	
    		}
    
    		return findSqrt (candidates, x, 0, length);
    	}
    
    	public int findSqrt(int[] candidates,int x,int lo, int hi)
    	{
    		if (lo == hi) { return 0; }
    		int mid = lo + (hi - lo) / 2;
    		double pow = Math.Pow (candidates [mid], 2);
    
    		double lowDiff = pow - (candidates [mid - 1] + candidates [mid]);
    		double upperDiff = pow + (candidates [mid] + candidates [mid + 1]);
    
    		if (x == pow || (x > pow && x < upperDiff)){
    			return mid;
    		} 
    
    		if (x < pow &&  x > lowDiff ) {
    			return mid - 1;
    		}
    
    		if (pow < x) {
    			return findSqrt (candidates, x, mid + 1, hi);
    		} else {
    			return findSqrt (candidates, x, lo, mid);
    		}
    	
    	}

  • 1

    The judger is throwing System.OutOfMemoryException when running your code. One line 11 you are doing:

    int[] candidates = new int[length + 1];
    

    This is probably where the problem lies. You are trying to allocate an array of size 2147395600, no wonder it will run out of memory.


  • 0
    C

    Thank you for reminding. I used an array to investigate the all iteration printing its interval values in screen, as you reminded. Solution should not use that big array. My mistake.


  • 0
    C

    I have solved it without using array, thank you. It used binary search and calculates tests in 60ms. Thank you 1337c0d3r

     public int MySqrt(int x) 
    	{
    		if (x == 0) { return 0; }
    		if (x >= 1 && x <= 3) { return 1; }
    		if (x >= 4 && x < 9) { return 2; }
    		if (x >= 9 && x < 16) { return 3; }
    		if (x >= 16 && x < 25) { return 4; }
    		if (x >= 25 && x < 36) { return 5; }
    
    		int length = x / 5;
    
    		return findSqrt (x, 0, length);
    	}
    
    	public int findSqrt(int x,int lo, int hi)
    	{
    		if (lo == hi) { return 0; }
    		int mid = lo + (hi - lo) / 2;
    		double pow = Math.Pow (mid, 2);
    
    		double lowDiff = pow - ((mid - 1) + mid);
    		double upperDiff = pow + (mid + mid + 1);
    
    		if (x == pow || (x > pow && x < upperDiff)){
    			return mid;
    		} 
    
    		if (x < pow &&  x > lowDiff ) {
    			return mid - 1;
    		}
    
    		if (pow < x) {
    			return findSqrt (x, mid + 1, hi);
    		} else {
    			return findSqrt (x, lo, mid);
    		}
    	
    	}

Log in to reply
 

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