Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Approach with binary search
With binary search, the
left pivot will be the integer value of sqrt. Remember don’t write the code like, this will trigger overflow for some inputs:
if(mid * mid == x)
Time complexity: $O(log(x))$.
Approach with newton methods
Newtons’ method is a clever method for computing the sqrt value, and we use
double type for the accuracy.
Preparing for an interview? Check out this!