69. Sqrt(x)

69. Sqrt(x)

Tag: Binary Search Math Bitwise Manipulation

Difficulty: Easy

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.

---

Example 1:

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

Example 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.

Constraints:

• 0 <= x <= 2³¹ - 1

---

Binary Search

Algorithm

1. If x < 2, return x.
2. Set the left boundary to 2, and the right boundary to x // 2.
3. While left <= right:

• Take num = (left + right) / 2 as a guess. Compute num * num and compare it with x:
  • If num * num > x, move the right boundary right = pivot - 1
  • Else, if num * num < x, move the left boundary left = pivot + 1
  • Otherwise num * num == x, the integer square root is here, let's return it

4. Return right

• Time complexity: O(log N).
• Space complexity: O(1).

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

        while lo <= hi:
            mi = lo + (hi - lo) // 2
            num = mi * mi

            if num < x:
                lo = mi + 1
            elif num > x:
                hi = mi - 1
            else:
                return mi
        
        return hi

Math

• Time complexity: O(1).
• Space complexity: O(1).

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

        lo = int(math.e ** (0.5 * math.log(x)))
        hi = lo + 1

        return hi if hi * hi <= x else lo

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        lo = self.mySqrt(x // 2 ** 2) * 2
        hi = lo + 1

        return hi if hi * hi <= x else lo

Bitwise & Recursion

• Time complexity: O(log N).
• Space complexity: O(log N).

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        '''
        lo = self.mySqrt(x // 2 ** 2) * 2
        '''
        lo = self.mySqrt(x >> 2) << 1
        hi = lo + 1

        return hi if hi * hi <= x else lo

Newton's Method

• Time complexity: O(log N).
• Space complexity: O(1).

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        x0 = x
        x1 = (x0 + x / x0) / 2

        while abs(x0 - x1) >= 1:
            x0 = x1
            x1 = (x0 + x / x0) / 2
        
        return int(x1)

---