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.

Intuition

The key insight is recognizing that we're searching for a specific integer value within a known range. Since we need to find the largest integer whose square doesn't exceed x, and we know this value must be between 0 and x itself (since 1 * 1 = 1 ≤ x for any x ≥ 1, and for larger values, the square root is always smaller than the number itself).

This naturally suggests a search problem. We could check every number from 0 to x sequentially, but that would be inefficient for large values of x.

Binary search comes to mind because:

1. We have a sorted range of candidates [0, 1, 2, ..., x]
2. We have a clear decision criterion: for any candidate mid, we can determine if it's too large (when mid * mid > x) or potentially valid (when mid * mid ≤ x)
3. The property is monotonic - if a number's square is too large, all larger numbers will also have squares that are too large

The tricky part is handling the "round down" requirement. When the exact square root isn't an integer, we want the largest integer that doesn't exceed the true square root. This is why we use the variant of binary search that finds the rightmost valid position - we keep l = mid when mid is valid (could be our answer) and only reduce the search space from the right when mid is too large.

To avoid overflow when computing mid * mid for large numbers, we rearrange the comparison to mid > x // mid, using integer division instead of multiplication.

Learn more about Math and Binary Search patterns.

Solution Approach

We implement a binary search algorithm to find the square root. The search maintains two pointers, l (left) and r (right), which define our search range.

Initialization:

• Set l = 0 as the minimum possible square root
• Set r = x as the maximum possible square root (though for x > 1, the actual square root is always less than x, this gives us a safe upper bound)

Binary Search Loop: The search continues while l < r:

1. Calculate the middle point: mid = (l + r + 1) >> 1

   • We use (l + r + 1) instead of (l + r) to bias toward the upper middle when the range has an even number of elements
   • The >> 1 operation is equivalent to dividing by 2 (right shift by 1 bit)

2. Check if mid is too large: if mid > x // mid

   • This is equivalent to checking if mid * mid > x but avoids potential integer overflow
   • We use integer division x // mid instead of multiplication

3. Adjust the search range:

   • If mid is too large (its square exceeds x): set r = mid - 1 to search in the lower half
   • Otherwise (its square is less than or equal to x): set l = mid to keep this valid candidate and search for potentially larger values

Why this variant of binary search? This implementation finds the rightmost position where the condition mid * mid ≤ x is satisfied. By keeping l = mid when the condition is met and using (l + r + 1) // 2 for the middle calculation, we ensure that:

• We always make progress (the range shrinks in each iteration)
• We converge to the largest valid integer square root

Return Value: When the loop ends (l == r), l contains the largest integer whose square doesn't exceed x, which is exactly the floor of the square root.

The time complexity is O(log x) since we halve the search space in each iteration, and the space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

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

Initial Setup:

• l = 0 (left boundary)
• r = 10 (right boundary)
• We're looking for the largest integer whose square ≤ 10

Iteration 1:

• Range: [0, 10]
• mid = (0 + 10 + 1) >> 1 = 11 >> 1 = 5
• Check: Is 5 > 10 // 5? → Is 5 > 2? → Yes, 5 is too large (since 5² = 25 > 10)
• Update: r = mid - 1 = 4

Iteration 2:

• Range: [0, 4]
• mid = (0 + 4 + 1) >> 1 = 5 >> 1 = 2
• Check: Is 2 > 10 // 2? → Is 2 > 5? → No, 2 is valid (since 2² = 4 ≤ 10)
• Update: l = mid = 2 (keep this valid candidate, search for larger)

Iteration 3:

• Range: [2, 4]
• mid = (2 + 4 + 1) >> 1 = 7 >> 1 = 3
• Check: Is 3 > 10 // 3? → Is 3 > 3? → No, 3 is valid (since 3² = 9 ≤ 10)
• Update: l = mid = 3 (keep this valid candidate)

Iteration 4:

• Range: [3, 4]
• mid = (3 + 4 + 1) >> 1 = 8 >> 1 = 4
• Check: Is 4 > 10 // 4? → Is 4 > 2? → Yes, 4 is too large (since 4² = 16 > 10)
• Update: r = mid - 1 = 3

Final State:

• l = r = 3
• Loop terminates
• Return 3

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

Solution Implementation

Time and Space Complexity

The time complexity of this binary search algorithm is O(log x). The algorithm repeatedly divides the search space in half by calculating the midpoint and adjusting either the left or right boundary based on whether mid * mid is greater than x. Since we're reducing the search space by half in each iteration, and starting with a range of size x, the number of iterations is proportional to log₂(x).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variables l, r, and mid, regardless of the input size x. No additional data structures or recursive calls are made that would increase memory usage as the input grows.

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

Common Pitfalls

1. Integer Overflow When Checking Mid-Square

The Pitfall: A common mistake is directly calculating mid * mid and comparing it with x:

if mid * mid > x:  # WRONG - can cause overflow!
    right = mid - 1

When mid is large, mid * mid can exceed the integer limit and cause overflow issues, leading to incorrect results.

The Solution: Use division instead of multiplication to avoid overflow:

if mid > x // mid:  # Correct - avoids overflow
    right = mid - 1

This mathematically equivalent check prevents overflow since we're dividing x by mid instead of multiplying mid by itself.

2. Incorrect Mid-Point Calculation Leading to Infinite Loop

The Pitfall: Using the standard mid-point calculation can cause an infinite loop:

mid = (left + right) // 2  # Can cause infinite loop!

When left = right - 1 and the answer is right, this formula gives mid = left, causing the algorithm to get stuck in an infinite loop since left never advances.

The Solution: Use the ceiling division for mid-point calculation:

mid = (left + right + 1) >> 1  # Correct - always makes progress

By adding 1 before dividing, we bias toward the upper middle, ensuring the search space always shrinks.

3. Division by Zero When x = 0

The Pitfall: The comparison mid > x // mid will cause a division by zero error when mid = 0 and we're checking it:

if mid > x // mid:  # Division by zero when mid = 0!

The Solution: Add a special check for mid = 0 or handle edge cases separately:

if mid == 0:
    left = mid + 1  # or handle x = 0 case separately
elif mid > x // mid:
    right = mid - 1
else:
    left = mid

Alternatively, handle x = 0 and x = 1 as special cases before the binary search.

4. Wrong Update Logic for Search Boundaries

The Pitfall: Incorrectly updating both boundaries to exclude mid:

if mid > x // mid:
    right = mid - 1
else:
    left = mid + 1  # WRONG - might skip the correct answer!

This can skip over the correct answer when mid * mid = x.

The Solution: Keep mid as a candidate when it's valid:

if mid > x // mid:
    right = mid - 1
else:
    left = mid  # Keep mid as a potential answer

This ensures we don't discard valid candidates during the search.