Share my fast Python solution based on Newton's method


  • 0
    D

    Based on Newton's method. Optimizations for performance:

    1. start from num/2 + 1;
    2. use a variable to store the calculated square to save one redundant calculation
    class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        '''
        Newton's method
        f(x) = x^2 - n --> f'(x) = 2x
        x1 = x0 - f(x0)/f'(x0) = x0 - (x0^2 - n) / (2x0)
        x1 = (x0^2 + n) / (2x0), or
        x1 = (x0 + n/x0)/2
        '''
        root = (num >> 1) + 1
        while True:
            square = root * root
            if square > num:
                root = (root + num/root) >> 1
            else:
                break
    
        return square == num

Log in to reply
 

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