3 JAVA solutions with explanation


  • 15

    The three solutions are as the follows, solution1 and solution3 are pretty straight forward.

     Look for the critical point: i * i <= x && (i+1)(i+1) > x
    

    A little trick is using i <= x / i for comparison, instead of i * i <= x, to avoid exceeding integer upper limit.

    Solution1 - Binary Search Solution: Time complexity = O(lg(x)) = O(32)=O(1)

    public int mySqrt(int x) {
    	if (x == 0) return 0;
    	int start = 1, end = x;
    	while (start < end) { 
    		int mid = start + (end - start) / 2;
    		if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result
    			return mid; 
    		else if (mid > x / mid)// Keep checking the left part
    			end = mid;
    		else
    			start = mid + 1;// Keep checking the right part
    	}
    	return start;
    }
    

    Solution2 - Newton Solution: Time complexity = O(lg(x))

    I think Newton solution will not be faster than Solution1(Binary Search), because i = (i + x / i) / 2, the two factors i and x / i are with opposite trends. So time complexity in the best case is O(lgx).

    Anyone can give the accurate time complexity? Appreciate it!

    public int mySqrt(int x) {
        if (x == 0) return 0;
    	long i = x;
    	while(i > x / i)  
    		i = (i + x / i) / 2;	    	
    	return (int)i;
    }
    

    Solution3 - Brute Force: Time complexity = O(sqrt(x))

    public int mySqrt(int x) { 
    	if (x == 0) return 0;
    	for (int i = 1; i <= x / i; i++) 		
    		if (i <= x / i && (i + 1) > x / (i + 1))// Look for the critical point: i*i <= x && (i+1)(i+1) > x
    			return i;		
    	return -1;
    }

Log in to reply
 

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