Problem Statement in English

You’re given a non-negative integer x. Compute and return the square root of x.

You cannot use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Approach

We can use binary search to guess the square root in $log(n)$ steps. We can start with a range of $[0, x]$ and check mid. If mid * mid is less than or equal to x, we can move the left pointer to mid + 1, otherwise we move the right pointer to mid - 1. We keep track of the last valid mid value as our answer.

And we’re done!

Solution in Python


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

        while l <= r:
            mid = (l + r) // 2

            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1

        return ans

Complexity

  • Time: $O(\log x)$
    Since we are using binary search, the time complexity is logarithmic in terms of the input value x.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables, the space complexity is constant.

And we are done.