Square of x

problem at: https://leetcode.com/problems/sqrtx

# 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

Newton's method gives the best runtime asymptotically.

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