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!
Join my Email List for more insights, It's Free!😋