Implement

`int sqrt(int x)`

.
Compute and return the square root of

*x*.Analysis:

According to Newton's Method(http://en.wikipedia.org/wiki/Newton's_method), we can use

to get the sqrt(x).

Code:

class Solution { public: int sqrt(int x) { // Start typing your C/C++ solution below // DO NOT write int main() function if (x==0) {return 0;} if (x==1) {return 1;} double x0 = 1; double x1; while (true){ x1 = (x0+ x/x0)/2; if (abs(x1-x0)<1){return x1;} x0=x1; } } };

Another solution: the binary search approach is a more general way of solving this problem. One thing you need to consider is the length of the input, since taking the mid of a big value and computing its square may overflow the int type.

We can use "long long" , which have a max value 2^63-1.

The max of an int is 2^15-1

The max of a long is 2^31-1

class Solution { public: int sqrt(int x) { // Start typing your C/C++ solution below // DO NOT write int main() function long long high = x; long long low = 0; if (x<=0) {return 0;} if (x==1) {return 1;} while (high-low >1){ long long mid = low + (high-low)/2; if (mid*mid<=x){low = mid;} else {high = mid;} } return low; } };

I believe in the interview, they won't expect you to remember Newtown's method. The solution they are expecting is a Binary Search method.

ReplyDeleteThanks for your kind advice!

DeleteThe binary search approach is added to this post.

This comment has been removed by the author.

DeleteQuoting on one line above "The max of an int is 2^15-1", int in most cases is 32 bit, unless for some specific platform.

ReplyDeleteIs there a reason that you use mid = low + (high-low)/2; rather than (high + low)/2; ?

ReplyDeleteYes, using high+low /2 may cause overflow errors, when high and low both are very big, high+low may exceed and cause the overflow error, while high-low will not.

DeleteThis comment has been removed by the author.

DeleteNice solution man. Although I think you need not worry about overflowing: both high and low are within the range [0 INT_MAX], so (high + low) is at most 2*INT_MAX, which can perfectly fit into a 'long long int' integer. So as long as you define high, low and mid as 'long long int', an overflow will never occur.

DeleteOr better yet, even if both low and high are defined as 'int', we are still good. Note that it is guaranteed that (int)sqrt(x) < (int)(x/2) for any x >= 6, therefore, for any large enough number, in the first iteration, we have low == 0, so (low + high) is always <= INT_MAX (no overflow). then we always have mid*mid > x, so it is always 'high = mid;' that will be executed in the first iteration, i.e. high <= INT_MAX / 2. From there on, both low and high will be within [0 INT_MAX/2] so (low + high) will never exceed INT_MAX.

Of course 'mid' must be defined as 'long long int' since we need to perform 'mid*mid', which may well exceed INT_MAX. But if we limit the initial value of 'high' to min(std::sqrt(INT_MAX) + 1, x/2), then it is safe to just define 'mid' as 'int'. std::sqrt(INT_MAX) is a constant that can be precomputed so it does not violate the requirement of this problem.

should u cast long to int int the end?

ReplyDeleteDecent improvement as (abs(x1-x0)<1) for Newton's Method.

ReplyDelete