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.

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(logn)O(\log{n})

Space Complexity: O(1)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 rr st.

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

.

To use Newton's method,

  • pick a initial value as r0=xr_0 = x. Why not use 0? because the derivative at 0 is 0, and Newton's method doesn't work.

  • update as

r1=r0f(r0)f(r0)=r0r02x2r0=(r0+xr0)/2r_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 r2<xr^2 < x the first time. (Why this condition work? because this process ensure the potential ansans approach to the solution monotonicly because f(r)f(r) is monotone for r>0r > 0)

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

Space Complexity: O(1)O(1)

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

Last updated