# Share my 2ms and 4lines JAVA code,

• 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.

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

• got it, over flow.

• This post is deleted!

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

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

• 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)`.

• 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.

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