Coder's Cat

2020-02-03

## Challenge Description

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.

Example 1:

Example 2:

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:

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!😋