Any folks passed this problem without using Math.sqrt?

Here is some solution from old discuss.
Jingfei Jia' Solution. Thanks jiangfei.
Just to explain newton method.
f(xn+delta) = f(xn) + f'(xn)delta + (1/2)f''(xn)*delta^2 + ...
keep first order,
f(xn+delta) = f(xn) + f'(xn)*delta = 0
delta =  f(xn)/f'(xn)
so
Xn+1 = Xn  f(Xn)/f'(Xn)
, iff(Xn) = X^2  n
,f'(x)=2x
Xn+1 = Xn  (Xn^2  n)/2Xn = Xn/2 + n/2Xn
There are 14 methods.
class Solution { public: int sqrt(int x) { double y,z(1.0); while(int(y)int(z)){ y=z; z=double(x)/2/y+y/2; } return int(y); } };
lchh's Solution. Thanks lchh.
Binary search.
class Solution { public: int sqrt(int x) { // Start typing your C/C++ solution below // DO NOT write int main() function if(x<=1) return x; int left=0, right=x, mid; while( (rightleft)>1 ) { mid=left+(rightleft)/2; if(mid==x/mid) return mid; else if(x/mid < mid) right=mid; else left=mid; } return left; } };

Java  includes protection against int overflow by setting to biggest square root possible for an int:
public int sqrt(int x) { int max = 46340; int min = 0; while (min+1 < max) { int candidate = (min+max)/2; if (candidate * candidate > x) { max = candidate; continue; } min = candidate; } if (max*max <= x) { return max; } return min; }

Solution of Netwon's method depends heavily on the initial guess of the solution value (ie the starting point of the newton iteration) so it doesn't guarantee to find the right solution.
Try this sqrt(183692038) using a starting value below 1000. The newton method will find 0 instead of 13553.

I wonder how you get this conclusion. I tried sqrt(183692038) with initial value of 900,700, even 1. I got the same correct value of 13553. In general, with the positive initial value you will get the +sqrt(x), with negative initial value you will get sqrt(x).
int sqrt(int x) {
double r = 1, last = 0;
while (abs(r  last) > 0.5) {
last = r;
r = (r+x/r)/2;
};
return (int)r;
}

This question does not make sense to me since we usually need a sqrt value with high precision ;), I provided my answer anyway. cast result to integer to just have a pass.
public int sqrt(int x){ if(x == 0  x == 1) return x; double epsilon = 0.001; double res = Math.round(sqrt((double)x, 0, (double)x, epsilon)); return (int)(res*res > x ? res1 : res); } public double sqrt(double x, double y, double target, double epsilon){ double guess = (x + y)/2; double guessValue = Math.abs(guess*guess  target); if(guessValue < epsilon){ return guess; }else if( guess * guess < target){ return sqrt(x,guess,target,epsilon); }else{ return sqrt(guess,y,target,epsilon); } }