#69

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Sqrt(x)

Solve the Sqrt(x) problem using binary search to find the integer square root of a number without built-in operators.

Problem Statement

Given a non-negative integer x, you need to return the square root of x rounded down to the nearest integer. The result should be non-negative, and you cannot use any built-in exponent functions or operators for the solution.

For example, when x is 4, the square root is exactly 2, so the output is 2. In contrast, when x is 8, the square root is approximately 2.82842, so rounding it down gives 2 as the correct output.

Examples

Example 1

Input: x = 4

Output: 2

The square root of 4 is 2, so we return 2.

Example 2

Input: x = 8

Output: 2

The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints

0 <= x <= 231 - 1

Solution Approach

Binary Search Approach

The optimal approach involves performing binary search over the valid answer space. Since we know that the square root of x lies between 0 and x, we can narrow down the range using binary search. For each mid-point in the range, we compare mid*mid with x to determine if the square root is smaller, larger, or equal.

Edge Cases

Consider edge cases like x = 0 or x = 1. These are straightforward since the square root of 0 is 0, and the square root of 1 is 1. You need to handle these efficiently without unnecessary computations.

Time Complexity Considerations

Using binary search reduces the problem's time complexity to O(log x), as we halve the search space at each step. This is a significant improvement over a linear search, which would take O(x) time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the binary search approach is O(log x), as we reduce the search space by half at each step. The space complexity is O(1), as only a few variables are used to track the binary search bounds and the result.

What Interviewers Usually Probe

The candidate understands binary search and can apply it in mathematical problems.
The candidate efficiently handles edge cases, like x = 0 and x = 1.
The candidate explains the reasoning behind the time complexity and avoids unnecessary brute-force solutions.

Common Pitfalls or Variants

Common pitfalls

Using built-in square root functions, which contradicts the problem constraints.
Not considering edge cases, especially when x is 0 or 1.
Misunderstanding the rounding requirement, failing to correctly handle non-perfect squares.

Follow-up variants

Implementing this with iterative search rather than binary search.
Handling very large values of x near the upper bound of the constraints.
Returning results in floating-point rather than integer form.

FAQ

What is the optimal approach for solving Sqrt(x)?

The optimal solution is binary search, which allows narrowing the search space for the square root efficiently without using built-in functions.

How do I handle edge cases like x = 0 or x = 1?

For x = 0, the square root is 0, and for x = 1, the square root is 1. These cases are straightforward and can be handled before applying binary search.

Why can't I use built-in exponentiation functions?

The problem explicitly asks not to use any built-in exponentiation functions or operators, which encourages you to implement a more fundamental approach such as binary search.

How do I ensure the output is rounded down to the nearest integer?

During the binary search, when you find a mid-point, you need to check if mid*mid is less than or equal to x. If it exceeds, adjust the bounds accordingly.

What is the time complexity of the binary search approach?

The time complexity of the binary search approach is O(log x), which is much more efficient than a brute force solution.

terminal

Solution

Solution 1: Binary Search

We define the left boundary of the binary search as $l = 0$ and the right boundary as $r = x$, then we search for the square root within the range $[l, r]$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        while l < r:
            mid = (l + r + 1) >> 1
            if mid > x // mid:
                r = mid - 1
            else:
                l = mid
        return l

Continue Practicing

#268 missing number #367 valid perfect square #400 nth digit