69_Sqrt(x)

[Easy] [Math]

Implementint 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)**2 > x, then mid is the solution.

• If mid**2 > x, then throw away right part.

• If mid**2 < x and (mid+1)**2 <= x, then throw away left part.

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

Space Complexity: $O(1)$

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 (or zeroes) of a real-valued function. In this problem, we want to find the floor of $r$ st.

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

.

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)$

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