Solutions

1. Brute Force

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0

        res = 1
        for i in range(1, x + 1):
            if i * i > x:
                return res
            res = i

        return res

Time & Space Complexity

Time complexity: $O(\sqrt {n})$
Space complexity: $O(1)$

2. In-Built Function

class Solution:
    def mySqrt(self, x: int) -> int:
        return int(sqrt(x))

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

3. Binary Search

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        res = 0

        while l <= r:
            m = l + (r - l) // 2
            if m * m > x:
                r = m - 1
            elif m * m < x:
                l = m + 1
                res = m
            else:
                return m

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Recursion

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x

        l = self.mySqrt(x >> 2) << 1
        r = l + 1
        return l if r ** 2 > x else r

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

5. Newton's Method

class Solution:
    def mySqrt(self, x: int) -> int:
        r = x
        while r * r > x:
            r = (r + x // r) >> 1
        return r

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$