Leetcode 69. Sqrt(x)

https://leetcode.com/problems/sqrtx/

Using math module is applicable but meaningless. The normal way to get square root is to use formula n + x/n = 2n, so n = sqrt(x). Of course we cannot set n to that value, but we can approach by recursion.

Solution:

# T:O(lgn) S:O(1)
class Solution:
    # @param {integer} x
    # @return {integer}
    def mySqrt(self, x):
        if x == 0: return 0
        y = x/2.0
        z = (y + x/y)/2
        while float(abs(z - y)) > 0.1:
            y = z
            z = (y + x/y)/2
        return int(z)

Run Time: 68 ms