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)
Recommendation Algorithm Flow for Sqrt(x)

Solution Approach

Binary search between 0 and x. Use mid > x / mid to avoid overflow instead of mid * mid > x.

function solution(x) {
  if (x < 2) return x;
  var lo = 1, hi = Math.floor(x / 2);
  while (lo <= hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (mid === Math.floor(x / mid)) return mid;
    if (mid < Math.floor(x / mid)) lo = mid + 1;
    else hi = mid - 1;
  }
  return hi;
}

Time O(log x), Space 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;
    }
}