Solution by bxr556


  • 2
    B

    Implement int sqrt(int x).

    Compute and return the square root of x. x is guaranteed to be a non-negative integer. You can't use Math.sqrt function.

    Example 1:

    Input:4
    Output:2
    

    Example 2:

    Input 8
    Output 2
    Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
    

    Approach #1 Brute Force [Accepted]

    Intuition

    Check all the integers up to x/2+1, find the maximum i where i*i<x.

    Java

    class Solution {
        public int mySqrt(int x) {
            if (x==0){
                return 0;
            }
            
            for (int i =1;i<=x/2+1;i++){
                if (i*i<=x && (double)(i+1)*(i+1)>x){
                    return i;
                }
            }
            return 0;
        }
    }
    

    Note: Please pay attention to Integer overflow. That's the reason why we convert the data type to double.

    Complexity Analysis

    • Time complexity : $$O(n)$$. For integer x, it takes on average x/2 steps to calculate the correct sqrt(x), hence the time complexity is O(n).
    • Space complexity : $$O(1)$$.

    Approach #2 Binary Division [Accepted]

    Algorithm

    This solution uses binary search approach.

    Java

    class Solution {
        public int mySqrt(int x) {
            if(x<2) return x;
    
            int start = 1;
            int end = 46340;
            int mid,sq;
            while(start<end){
                mid = start + (end - start)/2;
                sq = mid*mid;
    
                if(sq == x){
                    return mid;
                }else if(sq>x){
                    end = mid-1;
                }else {
                    start = mid+1;
                }
            }
            return start*start>x?start-1:start;
        }
    }
    
    

    Complexity Analysis

    • Time complexity : $$O(log n)$$. For each element x, it will take log n time.

    • Space complexity : $$O(1))$$.


    Approach #3 Newton's method [Accepted]

    Algorithm

    This solution uses Newton's method. Here are some links related to Newton's iteration for computing sqrt of X.

    It is based on the fact that sqrt will be less than the half of the number.

    Java

    class Solution {
        public int mySqrt(int x) {
            if (x>=2147395600){
                return 46340;
            }
            int ub=x;
            int lb=1;
            while(ub>lb)
            {
                ub=(int)Math.floor((lb+ub)/2);
                lb=(int)Math.floor(x/ub);
            }
            return ub;
        }
    }
    

    Complexity Analysis

    • Time complexity : Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with n-digit precision, provided that a good initial approximation is known, is $$O((\log n) F(n))$$ where F(n) is the cost of calculating f(x)/f'(x), with n-digit precision.

    • Space complexity : $$O(1))$$.


  • 0
    A

    IMO this is more readable for the brute force solution

    class Solution {
        public int mySqrt(int x) {
            if (x==0){
                return 0;
            }
    
            for (int i =1;i<=x/2+1;i++){
                if(x/i == i) return i;
                if( x/i < i ) return i-1;
            }
            return 0;
        }
    }
    

Log in to reply
 

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