69. Sqrt(x) - Explanation

Problem Link

Description

You are 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 = 9

Output: 3

Example 2:

Input: x = 13

Output: 3

Constraints:

• 0 <= x <= ((2^31)-1)

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The square root of a number x is the largest integer i such that i * i <= x. We can find this by simply checking each integer starting from 1 until squaring it exceeds x. The answer is the last integer whose square did not exceed x.

Algorithm

1. Handle the edge case where x is 0 by returning 0.
2. Initialize res to 1 to track the potential answer.
3. Iterate from 1 to x. For each integer i, check if i * i > x.
4. If i * i > x, return the previous valid result res.
5. Otherwise, update res = i and continue.
6. Return res after the loop.

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

Intuition

Most programming languages provide a built-in square root function that computes the result efficiently using optimized mathematical algorithms (often Newton's method or similar). We can leverage this and simply truncate the result to get the integer floor of the square root.

Algorithm

1. Call the language's built-in square root function on x.
2. Convert the result to an integer (truncating any decimal part).
3. Return the integer result.

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

Intuition

Since we are looking for the largest integer whose square is at most x, and the squares of integers are monotonically increasing, we can use binary search. The search space is [0, x], and we narrow it down by checking if the middle value squared is less than, greater than, or equal to x.

Algorithm

1. Initialize l = 0, r = x, and res = 0 to store the answer.
2. While l <= r:
   • Compute middle m = l + (r - l) / 2.
   • If m * m > x, the answer must be smaller, so set r = m - 1.
   • If m * m < x, m is a valid candidate. Store it in res and search for a larger value by setting l = m + 1.
   • If m * m == x, we found the exact square root, so return m.
3. Return res after the loop.

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

Intuition

We can exploit a mathematical property: sqrt(x) = 2 * sqrt(x / 4). By right-shifting x by 2 bits (dividing by 4), we recursively compute the square root of a smaller number. Then we left-shift the result by 1 (multiply by 2) to scale it back up. Finally, we check if incrementing by 1 still gives a valid square root.

Algorithm

1. Base case: if x < 2, return x (since sqrt(0) = 0 and sqrt(1) = 1).
2. Recursively compute l = mySqrt(x >> 2) << 1. This gets an approximate lower bound.
3. Compute r = l + 1 as the candidate one larger.
4. If r * r > x, return l. Otherwise, return r.

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

Intuition

Newton's method is a numerical technique for finding roots of equations. To find sqrt(x), we solve r^2 = x, or equivalently find the root of f(r) = r^2 - x. Newton's iteration formula gives us r_new = (r + x/r) / 2. Starting with an initial guess of x, we repeatedly apply this formula until r^2 <= x, which converges quickly to the answer.

Algorithm

1. Initialize r = x as the starting guess.
2. While r * r > x, update r = (r + x / r) / 2 (using integer division, or right shift by 1).
3. The loop converges when r^2 <= x.
4. Return r as the integer square root.

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)$

---

Common Pitfalls

Integer Overflow When Squaring

When computing m * m during binary search, the result can overflow if m is large (e.g., close to 46340 for 32-bit integers). Always cast to a 64-bit type before multiplication, such as (long)m * m in Java or (long long)m * m in C++, to prevent incorrect comparisons.

Off-by-One Errors in Binary Search

A subtle mistake is returning m when m * m < x instead of tracking it as a candidate and continuing to search for a larger valid value. The correct approach is to store m in a result variable when m * m <= x and keep searching, returning the stored result when the loop ends.