Code Logo

Sqrt(x)

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given a non-negative integer x, compute and return its square root rounded down to the nearest integer. You may not use any built-in exponent functions like pow(x, 0.5) or x ** 0.5. The algorithm must run in O(log x) time.

The square root of x lies in the range [0, x]. Binary search narrows this range by checking if the square of the middle value is less than, equal to, or greater than x. If mid * mid == x, we found the exact root. If mid * mid < x, the root is larger, so we search the right half. If mid * mid > x, the root is smaller, so we search the left half.

A critical implementation detail is overflow:mid * mid can exceed 32-bit integer limits when x is large (up to 2³¹ - 1). Use long(64-bit) for the multiplication, or check mid > x / mid instead of mid * mid > x to avoid overflow. The latter comparison is safer and avoids type promotion entirely.

Edge cases include x = 0 (return 0), x = 1 (return 1), and very large values near Integer.MAX_VALUE where overflow would occur without the division-based check.

The binary search approach for square root is also known as Newton's method adapted for integer arithmetic. Since the square root function is monotonic (if m² > x then any larger n also satisfies n² > x), binary search correctly narrows the range. The division-based comparison x / mid avoids integer overflow when mid is large.

Example Input & Output

Example 1
Input
2147395599
Output
46339
Explanation

Large value: floor sqrt test.

Example 2
Input
8
Output
2
Explanation

Floor sqrt of 8 is 2 (2*2=4, 3*3=9>8).

Example 3
Input
4
Output
2
Explanation

Square root of 4 is exactly 2.

Example 4
Input
0
Output
0
Explanation

Square root of 0 is 0.

Example 5
Input
1
Output
1
Explanation

Square root of 1 is 1.

Algorithm Flow

Recommendation Algorithm Flow for Sqrt(x)

Solution Approach

Compute the integer square root of a non-negative integer x without using built-in sqrt functions. Return the largest integer whose square is less than or equal to x. Use binary search on the range [0, x]. For each midpoint, compute mid * mid and compare with x. If mid*mid equals x, return mid. If mid*mid is too small, search the right half; if too large, search the left half. When the loop ends, right holds the floor square root.

function mySqrt(x) {
  if (x < 2) return x;
  var left = 1, right = Math.floor(x / 2);
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    var sq = mid * mid;
    if (sq === x) return mid;
    if (sq < x) left = mid + 1;
    else right = mid - 1;
  }
  return right;
}

The upper bound can be reduced to x/2 since sqrt(x) <= x/2 for x > 1. The search narrows down the integer whose square best approximates x from below. For non-perfect squares like 8, the result is 2 since 2*2=4 <= 8 but 3*3=9 > 8.

Time complexity is O(log n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int x) {
        if (x < 2) return x;
        int lo = 1, hi = x / 2;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid == x / mid) return mid;
            if (mid < x / mid) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }
}