Modified Newton's Method to return int


  • 0
    Y
    class Solution:
    # @param x, an integer
    # @return an integer
        def sqrt(self, x):
            i=x
            while i!=0:
                j=(i+x/i)/2
                if j>=i:
                    return i
                i=j
            return i
    

    Assume the root is r. If i>r, then x/i<r<i, so j<i, so we should return i when j>=i.


Log in to reply
 

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