Solution for sqrt(int x)


  • 0
    S

    We can you Newton`s method to solve it. Using the fact that sqrt will be less than the half the number, we can find it by binary search

    int mySqrt(int x) {
            int ub=x;
            int lb=1;
            while(ub>lb)
            {
                ub=floor((lb+ub)/2);
                lb=floor(x/ub);
            }
            return ub;
        }
    

  • 0
    G

    public int mySqrt(int x) {
    if(x < 4) return x == 0 ? 0 : 1;
    int res = 2 * mySqrt(x/4);
    if((res+1) * (res+1) <= x && (res+1) * (res+1) >= 0) return res+1;
    return res;
    }


Log in to reply
 

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