69. Sqrt(x)

Problem Description

Given a non-negative integer x, you need to find and return the square root of x rounded down to the nearest integer. The returned value should be non-negative.

The key constraint is that you cannot use any built-in exponent functions or operators. For example, you cannot use pow(x, 0.5) in C++ or x ** 0.5 in Python.

Essentially, you need to find the largest integer result such that result * result ≤ x.

For example:

If x = 4, the square root is exactly 2, so return 2
If x = 8, the actual square root is approximately 2.828, but since we round down, return 2

The solution uses binary search to efficiently find this value. The algorithm searches in the range [0, x] and repeatedly checks the middle value. If mid * mid > x (written as mid > x // mid to avoid overflow), the answer must be smaller, so we search in the left half. Otherwise, the current mid could be the answer or we need to search for a larger value, so we search in the right half including mid.

The binary search continues until the left and right boundaries converge, at which point l contains the largest integer whose square is less than or equal to x.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

We need to find the largest integer whose square is ≤ x. This is a boundary-finding problem.

Think of the range [0, 1, 2, ..., x] with a boolean pattern:

false for values where mid * mid > x (too large)
true for values where mid * mid > x (first value that exceeds)

The pattern is: false, false, ..., false, true, true, ..., true

We want to find the first true - the first value where mid * mid > x. The answer is then first_true_index - 1.

Feasible Function: mid * mid > x (or equivalently mid > x / mid to avoid overflow)

Using the binary search template:

When mid * mid > x, mid is too large, so we record it as a potential "first too large" and search left
When mid * mid <= x, mid could be our answer, so we search right

After finding the first index where mid * mid > x, we subtract 1 to get the largest valid square root.

Edge Case: If first_true_index == -1, all values up to x have squares ≤ x, which only happens when x >= x * x, meaning x <= 1. We handle this by returning x directly for these cases.

To avoid overflow when computing mid * mid, we use the equivalent comparison mid > x / mid.

Learn more about Math and Binary Search patterns.

Solution Implementation

1class Solution:
2    def mySqrt(self, x: int) -> int:
3        """
4        Find the integer square root using the binary search template.
5        Finds the first value where mid * mid > x, then returns mid - 1.
6        """
7        # Handle edge case
8        if x == 0:
9            return 0
10
11        left, right = 1, x
12        first_true_index = -1
13
14        while left <= right:
15            mid = (left + right) // 2
16            # Feasible: mid * mid > x (using division to avoid overflow)
17            if mid > x // mid:
18                first_true_index = mid
19                right = mid - 1
20            else:
21                left = mid + 1
22
23        # If first_true_index is -1, no value has mid * mid > x
24        # This happens when x <= 1, return x
25        if first_true_index == -1:
26            return x
27        return first_true_index - 1
28

1class Solution {
2    public int mySqrt(int x) {
3        // Handle edge case
4        if (x == 0) {
5            return 0;
6        }
7
8        int left = 1;
9        int right = x;
10        int firstTrueIndex = -1;
11
12        while (left <= right) {
13            int mid = left + (right - left) / 2;
14
15            // Feasible: mid * mid > x (using division to avoid overflow)
16            if (mid > x / mid) {
17                firstTrueIndex = mid;
18                right = mid - 1;
19            } else {
20                left = mid + 1;
21            }
22        }
23
24        // If firstTrueIndex is -1, no value has mid * mid > x
25        // This happens when x <= 1, return x
26        if (firstTrueIndex == -1) {
27            return x;
28        }
29        return firstTrueIndex - 1;
30    }
31}
32

1class Solution {
2public:
3    int mySqrt(int x) {
4        // Handle edge case
5        if (x == 0) {
6            return 0;
7        }
8
9        int left = 1;
10        int right = x;
11        int firstTrueIndex = -1;
12
13        while (left <= right) {
14            int mid = left + (right - left) / 2;
15
16            // Feasible: mid * mid > x (using division to avoid overflow)
17            if (mid > x / mid) {
18                firstTrueIndex = mid;
19                right = mid - 1;
20            } else {
21                left = mid + 1;
22            }
23        }
24
25        // If firstTrueIndex is -1, no value has mid * mid > x
26        // This happens when x <= 1, return x
27        if (firstTrueIndex == -1) {
28            return x;
29        }
30        return firstTrueIndex - 1;
31    }
32};
33

1/**
2 * Calculates the square root of a non-negative integer x using the binary search template.
3 * Finds the first value where mid * mid > x, then returns mid - 1.
4 */
5function mySqrt(x: number): number {
6    // Handle edge case
7    if (x === 0) {
8        return 0;
9    }
10
11    let left: number = 1;
12    let right: number = x;
13    let firstTrueIndex: number = -1;
14
15    while (left <= right) {
16        const mid: number = Math.floor((left + right) / 2);
17
18        // Feasible: mid * mid > x (using division to avoid overflow)
19        if (mid > Math.floor(x / mid)) {
20            firstTrueIndex = mid;
21            right = mid - 1;
22        } else {
23            left = mid + 1;
24        }
25    }
26
27    // If firstTrueIndex is -1, no value has mid * mid > x
28    // This happens when x <= 1, return x
29    if (firstTrueIndex === -1) {
30        return x;
31    }
32    return firstTrueIndex - 1;
33}
34

Solution Approach

We use the standard binary search template to find the first value where mid * mid > x, then subtract 1.

Template Structure:

left, right = 1, x
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if mid > x // mid:  # feasible: mid * mid > x (overflow-safe)
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

# Answer is first_true_index - 1, or x if first_true_index == -1

Feasible Condition: mid > x // mid (equivalent to mid * mid > x)

This finds the first value whose square exceeds x. The square root is one less than this value.

Algorithm Steps:

Handle edge case: if x == 0, return 0
Initialize left = 1, right = x, first_true_index = -1
While left <= right:
- Calculate mid = (left + right) // 2
- If mid > x // mid: record mid as potential answer, search left
- Else: search right
Return first_true_index - 1 if first_true_index != -1, else return x

Why Use Division Instead of Multiplication:

Comparing mid > x // mid instead of mid * mid > x prevents integer overflow. For large values of mid, mid * mid can exceed the integer limit.

Time Complexity: O(log x) - we halve the search space in each iteration Space Complexity: O(1) - only using constant extra space

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through finding the square root of x = 10 using the binary search template.

Initial Setup:

left = 1, right = 10, first_true_index = -1
We're looking for the first value where mid * mid > 10

Iteration 1:

left = 1, right = 10
mid = (1 + 10) // 2 = 5
Check: Is 5 > 10 // 5? → Is 5 > 2? → Yes, 5² = 25 > 10
first_true_index = 5, right = 4

Iteration 2:

left = 1, right = 4
mid = (1 + 4) // 2 = 2
Check: Is 2 > 10 // 2? → Is 2 > 5? → No, 2² = 4 ≤ 10
left = 3

Iteration 3:

left = 3, right = 4
mid = (3 + 4) // 2 = 3
Check: Is 3 > 10 // 3? → Is 3 > 3? → No, 3² = 9 ≤ 10
left = 4

Iteration 4:

left = 4, right = 4
mid = (4 + 4) // 2 = 4
Check: Is 4 > 10 // 4? → Is 4 > 2? → Yes, 4² = 16 > 10
first_true_index = 4, right = 3

Termination:

left = 4, right = 3, loop ends
first_true_index = 4
Return first_true_index - 1 = 3

Verification: 3² = 9 ≤ 10 and 4² = 16 > 10, so 3 is correct (floor of √10 ≈ 3.162).

Edge Case: x = 0

Return 0 directly (special case)

Edge Case: x = 1

For x=1: mid=1, is 1 > 1/1? Is 1 > 1? No.
first_true_index remains -1, so return x = 1
sqrt(1) = 1, correct!

Time and Space Complexity

Time Complexity: O(log x). The algorithm uses the binary search template with while left <= right. In each iteration, either left = mid + 1 or right = mid - 1, halving the search range. Maximum iterations: log₂(x).

Space Complexity: O(1). The algorithm uses only constant extra space for variables (left, right, mid, firstTrueIndex), regardless of input size. No recursive calls or additional data structures.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using while left < right with left = mid instead of the standard template.

Example of the Issue:

# Non-standard variant (confusing)
while left < right:
    mid = (left + right + 1) // 2
    if mid > x // mid:
        right = mid - 1
    else:
        left = mid
return left

Solution: Use the standard template to find first value where mid * mid > x:

left, right = 1, x
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if mid > x // mid:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1 if first_true_index != -1 else x

2. Integer Overflow When Checking Mid-Square

The Pitfall: Directly calculating mid * mid:

if mid * mid > x:  # Can overflow!

Solution: Use division instead:

if mid > x // mid:  # Overflow-safe

3. Not Handling x = 0 Edge Case

The Pitfall: When x = 0, starting with left = 1 causes an incorrect result.

Solution: Handle x = 0 as a special case:

if x == 0:
    return 0

4. Forgetting to Handle first_true_index = -1

The Pitfall: When x = 1, no value has mid * mid > x in range [1, 1].

Solution: Check for -1 and return x:

if first_true_index == -1:
    return x
return first_true_index - 1

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems