69.Sqrt(x)

Tags: [math], [newton_method], [approximation], [binary_search]

Com: {fb}

Link: https://leetcode.com/problems/sqrtx/#/description

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: Binary Search

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise ValueError('the input is invalid')
        if x == 0:
            return 0

        # binary search
        start = 0
        end = sys.maxint
        while start <= end:
            mid = start + (end - start) / 2
            mid_square = mid * mid
            if mid_square == x:
                return mid
            elif mid_square < x:
                if mid + 1 > end or ((mid + 1) * (mid + 1) > x):
                    return mid
                start = mid + 1
            else:
                # mid_square > x
                end = mid - 1

        return None

Revelation:

• The function require returning an integer, not a float, so if we can find mid * mid == x or mid * mid < x < (mid + 1) * (mid + 1), then we can just return mid.

Note:

• Time complexity = O(lgn).

Solution: Math, Newton's Method

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise ValueError('the input is invalid')
        if x == 0:
            return 0

        return self.my_sqrt_helper(x)

    def my_sqrt_helper(self, n):
        guess_x = n / 2.0
        better_x = self.improve_x(guess_x, n)

        while abs(guess_x - better_x) > 0.001:
            guess_x = better_x
            better_x = self.improve_x(guess_x, n)

        return int(better_x)

    def improve_x(self, guess_x, n):
        # y = x^2 - n
        guess_y = guess_x ** 2 - n

        # derivate: y' = 2*x, slope = y'
        slope = 2 * guess_x

        # tangent: y = slope * x + c
        #          c = y - slope * x
        c = guess_y - (2 * guess_x) * guess_x

        # so tangent: y = (2 * guess_x) * x + (guess_y - (2 * guess_x) * guess_x)
        # let y = 0, x = -(guess_y - (2 * guess_x) * guess_x) / (2 * guess_x)
        better_x = -(guess_y - (2 * guess_x) * guess_x) / (2 * guess_x)
        return better_x

Revelation:

• Derivative is the slope, is not tangent, the tangent is y = slope * x + c.
• Reference: https://zhaonanli.gitbooks.io/algorithm/content/newtons-method.html

Note:

• Time complexity = O(lgn * Fn), Fn is the time cost of calculating the f(x) / f'(x) with n-digit precision.