Approach 1: Newton’s Method
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
x1 = x
while True:
x0 = x1
x1 = (x0 + x / x0) / 2
if abs(x0 - x1) < 1:
break
return int(x1)Complexity
Time:
Space: