Python solution using Newton's method


  • 3
    C
    class Solution(object):
        def isPerfectSquare(self, num):
            """
            :type num: int
            :rtype: bool
            """
            if num < 0: return False
            if num <= 1: return True
            n = num/2  # start guessing using n = num/2
            while n*n!= num:
                inc = (num-n*n)/(2*n)
                n += inc
                if -1 <= inc <= 1: break
            if n*n < num: n+=1
            if n*n > num: n-=1
            return n*n == num
    

    f(x) = x^2 (find x that f(x) = num)

    f'(x) = 2*x

    start process with x = n (any positive number)

    if f(x) != num, update x = x + (num - f(x))/f'(x) = x + (num - n^2)/(2n)


  • 0
    J

    Don't know how others do it. But this is most standard way to do Newton's method. The good code comments itself.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.