Leetcode 69. Sqrt(x)

Problem

Leetcode 69 - Sqrt(x)

Example:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Approach

We can use binary search from 1 to x

• if mid * mid == x, return mid
• if mid * mid < x, update left pointer
• if mid * mid > x, update right pointer

Here is the Python code for the solution:

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 1, x
        res = 0

        while left <= right:
            mid = (left+right) // 2

            if mid * mid < x:
                left = mid + 1
                # we want to update res in case sqrt(x) needs to be rounded off
                res = mid
            elif mid * mid > x:
                right = mid - 1
            else:
                return mid

        return res    

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$