# 69\_Sqrt(x)

\[Easy] \[Math]

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:**

```
Input: 4
Output: 2
```

**Example 2:**

```
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
```

## Solution 1: Binary Search

**Idea**:

* If mid\*\*2 <= x and (mid+1)**\*\***&#x32; > x, then mid is the solution.
* If mid\*\*2 > x, then throw away right part.
* If mid\*\*2 < x and (mid+1)**\*\***&#x32; <= x, then throw away left part.

**Time Complexity**: $$O(\log{n})$$

**Space Complexity**: $$O(1)$$

```python
def mySqrt(x):
    """
    :type x: int
    :rtype: int
    """
    left, right = 0, x
    while left <= right:
        mid = left + (right - left)//2
        if mid**2 <= x and (mid+1)**2 > x:
            return mid
        elif mid**2 > x:
            right = mid - 1
        else:
            left = mid + 1
```

## Solution 2: Newton's method

**Idea**:

**Newton's method** is a method for finding successively better approximations to the [roots](https://en.wikipedia.org/wiki/Root_of_a_function) (or zeroes) of a [real](https://en.wikipedia.org/wiki/Real_number)-valued [function](https://en.wikipedia.org/wiki/Function_\(mathematics\)). In this problem, we want to find the floor of $$r$$ st.

$$
f(r) = r^2 - x = 0
$$

.

![](https://3090628744-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2dsVc5xyZikcYndiZI%2F-M2dsXTzDpOnveRjaLWN%2F-M2dsmKeskBVzyqcosk5%2FScreen%20Shot%202018-01-02%20at%2011.44.44%20AM.png?generation=1584471954576153\&alt=media)

To use Newton's method,

* **pick a initial value as** $$r_0 = x$$. Why not use 0? because the derivative at 0 is 0, and Newton's method doesn't work.
* update as

$$
r_1 = r_0 - \frac{f(r_0)}{f^{'}(r_0)}= r_0 - \frac{r_0^2 - x}{2r_0} = (r_0 + \frac{x}{r_0})/2
$$

use floor instead of the real value, until we have $$r^2 < x$$ the first time. (Why this condition work? because this process ensure the potential $$ans$$ approach to the solution monotonicly because $$f(r)$$ is monotone for $$r > 0$$)

**Time Complexity**: $$O(\log{n})$$

**Space Complexity**: $$O(1)$$

```python
def mySqrt(x):
    """
    :type x: int
    :rtype: int
    """
    ans = x
    while ans**2 > x:
        ans = (ans + x/ans) // 2
    return ans
```
