Square of x

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):

x=elog12x\sqrt{x} = e^{\log \frac{1}{2}x}

Complexity:

  • Time: O(1)O(1)
  • Space: O(1)O(1)
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 x<2x < 2, return xx.

For x2x \ge 2, x\sqrt{x} is always smaller than x2\frac{x}{2} and larger than 0: 0<a<x20 < a < \frac{x}{2}.

Complexity:

  • Time: O(logN)O(\log N)
  • Space: O(1)O(1)
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:

mySqrt(x)=2×mySqrt(x/4)mySqrt(x) = 2 \times mySqrt(x/4)

Could continue to optimize by bit shifts:

mySqrt(x)=mySqrt(x>>2)<<1mySqrt(x)=mySqrt(x> >2)< <1

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:

xn+1=xnf(xn)f(xn)=xnxn2a2xn=12(2xn(xnaxn))=12(xn+axn)x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}=x_{n}-\frac{x_{n}^{2}-a}{2 x_{n}}=\frac{1}{2}\left(2 x_{n}-\left(x_{n}-\frac{a}{x_{n}}\right)\right)=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right)

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 intx\texttt{int} \sqrt{x} 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: 7/19/2020, 3:45:14 PM