## # Problem ## # Solution

There are so many of them! Thanks to this question that I review Newton's method in Calculus.

Binary search may be easiest to write in an interview.

### # Pocket Calculator Algorithm

Based on the formula (hard to come up with if haven't seen before):

Complexity:

• Time:
• Space:
from math import e, log
def mySqrt(self, x):
if x < 2:
return x

left = int(e**(0.5 * log(x)))
right = left + 1
return left if right * right > x else right


If , return .

For , is always smaller than and larger than 0: .

Complexity:

• Time:
• Space:
def mySqrt(self, x):
if x < 2:
return x

left, right = 2, x // 2

while left <= right:
pivot = left + (right - left) // 2
num = pivot * pivot
if num > x:
right = pivot -1
elif num < x:
left = pivot + 1
else:
return pivot

return right


### # Recursion + Bit Shifts

Recursion is based on the formula:

Could continue to optimize by bit shifts:

def mySqrt(self, x):
if x < 2:
return x

left = self.mySqrt(x >> 2) << 1
right = left + 1
return left if right * right > x else right


### # Newton's Method

The math is deduced below:

The following 3 solutions all use Newton's method in different forms.

#### # initialize sqrt to x//2

Given the fact in binary search, return x if x < 2; o.w., x//2 is an upper bound for and the in the while loop sqrt monotonically decreases in every iteration.

    def mySqrt(self, x: int) -> int:
# Newton's method
if (x<2): return x
sqrt = x//2
while not (sqrt*sqrt<=x and (sqrt+1)**2>x):
sqrt = (sqrt + x//sqrt)//2
return sqrt


#### # initialize sqrt to x

In the while loop, sqrt monotonically decreases in every iteration.

    def mySqrt(self, x: int) -> int:
# Newton's method
sqrt = x
while sqrt**2>x:
sqrt = (sqrt + x//sqrt)//2
return sqrt


#### # initialize y & z

The proof is sinuous and runtime is slower than the previous two solutions.

    def mySqrt(self, x: int) -> int:
# Newton's method
y = 1
z = x
while (z>y):
z = (z+y)//2
y = x//z
return z

Last Updated: 4/6/2020, 4:15:22 PM