Any folks passed this problem without using Math.sqrt?


  • 1
    W

    Kindly provide hint for implementing your own sqrt.
    thanks!


  • 21
    S

    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), if f(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( (right-left)>1 )
      {
        mid=left+(right-left)/2;
    
        if(mid==x/mid)
          return mid;
        else if(x/mid < mid)
          right=mid;
        else
          left=mid;
      }
    
      return left;
    } 
    };

  • 0
    A

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

  • 0
    L

    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.


  • 0
    W

    How about this:

    class Solution {
    public:
    int sqrt(int x) {
        assert(x >= 0);
        if(x < 2)
            return x;
        int r = x;
        for(;;){
            int t = ((unsigned int)x / r + r) / 2;
            if(t >= r)
                break;
            r = t;
        }
        return r;
    }
    };

  • 0
    Q

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


  • 0
    Y

    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 ? res-1 : 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);
    	}
    	
    }

  • 0
    P

    This is my answer, using C++

    int sqrt(int x) {
    	int i = 14;
    	double base = (1 << 15) * (1 << 15) <= x ? 1 << 15 : 0;
    	for (; i >= 0; i--)
    	{
    		if ((base + (1 << i)) * (base + (1 << i)) <= x && (base + (1 << i + 1)) * (base + (1 << i + 1)) > x)
    			base += 1 << i;
    	}
    	return base;
    }

  • 0
    F
    class Solution {
    public:
        int sqrt(int x) {
        	if (x <  2) return x;
    		int start = 0; //if start =1, may overflow
    		int end = x;
    		int mid;
    		while (start != end-1) {
    			mid = (start + end)/2;
    			if (mid == x/mid) return mid;
    			else mid < x/mid ? start = mid : end = mid;
    		}
    		return start;
        }
    };

Log in to reply
 

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