367.Valid Perfect Square

Tags: [math], [newton's_method]

Link: https://leetcode.com/problems/valid-perfect-square/#/description

Given a positive integernum, write a function which returns True ifnumis a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

Solution: Math, Newton's method

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num < 0:
            return False

        sqrt = int(self.get_sqrt(num))
        return sqrt ** 2 == num

    def get_sqrt(self, n):
        approximate = n / 2.0
        better = self.improve_approximate(n, approximate)

        while abs(better - approximate) > 0.0001:
            approximate = better
            better = self.improve_approximate(n, approximate)

        return better

    def improve_approximate(self, n, approximate):
        n = float(n)
        approximate = float(approximate)

        # Newton's method simplification: x = (x_0) - (f(x_0) / f'(x_0))
        # f(x_0) = x_0^2 - n, f'(x_0) = 2 * x_0.
        # here approximate is x_0.
        return approximate - ((approximate ** 2 - n) / (2.0 * approximate))

Revelation:

• The explanation of Newton's method is here https://zhaonanli.gitbooks.io/algorithm/content/newtons-method.html

Note:

• Time complexity depends on the time complexity of using Newton's method to get square root.