Share my 2ms and 4lines JAVA code,


  • 26
    W

    My idea is, for any non-negative number N, sqrt(N) = 2/2sqrt(N) =2sqrt(1/4)sqrt(N) = 2sqrt(N/4). And for the Ns that are not multiple of 4, for example, 9, 25 or 49, the actual result should be 1+2*sqrt(N/4), because we need to take remainders into account.

    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;
    }
    

    Hope it helps.


  • 0
    J

    Could you please explain why (res+1)*(res+1)>=0, I don't quite get it


  • 0
    J

    got it, over flow.


  • 0
    M
    This post is deleted!

  • 0
    H

    (res+1) * (res+1) >= 0

    Shouldn't this statement be true for all conditions as long as res is a real number?


  • 1
    H

    FYI
    The line (res+1)*(res+1)>=0 is used because res+1 may be larger than sqrt(Ingeger.MAX_VALUE) so as to cause overflow and make the product negative.
    In fact, there is a more elegant way to do this (res+1) <= x / (res+1).


  • 0
    D

    Someone may ask why (res + 1) and res can cover all situations. Let's say, sqrt(target) = sqrt(4x+y), x and y are integers and 0 <= y <= 3, and say sqrt(x) = b, then b^2<= x <= b^2+2b. Thus, 2b = sqrt(4b^2) <= sqrt(4x+y) <=sqrt(4b^2+8b+3) < sqrt(4b^2+8b+4) = 2(b+2). Hence, sqrt(4x+y) could be either b or b+1, but could not be b+2.


Log in to reply
 

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