69. Sqrt(x)


  • 0
    U

    Newton method. Initial guess of x. Iteratively update guess to be average of previous guess and x // guess. Since guess is too high, x guess is too low.Terminate when guess^2 <= x. Time - O((log x)^3) - log x from nb iterations, log x from multiple and log x from divide Space - O(1)

    class Solution:
    def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    guess = x
    while guess * guess > x:
    guess = (guess + x // guess) // 2
    return guess


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.