Compute the Floor of a Number's Square Root
Solve this Problem
Given a non-negative integer
x, return the floor of its square root — the largest integer whose square doesn't exceed x — without using any built-in power or square-root function.
The candidate answers 0 through x split cleanly into "square ≤ x" and "square > x", in that order, which makes this a binary search over the answer itself rather than over an array.
Test Case 1:
Input:x = 8
Output:2
Explanation:√8 ≈ 2.828 — floored down to 2.
Test Case 2:
Input:x = 4
Output:2
Explanation:4 is a perfect square, so its square root is exact.
Test Case 3:
Input:x = 0
Output:0
Explanation:√0 = 0.
Constraints
- ◆
0 ≤ x ≤ 2³¹ - 1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public int mySqrt(int x) { |
| 3 | int lo = 0, hi = x, ans = 0; |
| 4 | while (lo <= hi) { |
| 5 | int mid = lo + (hi - lo) / 2; |
| 6 | if ((long) mid * mid <= x) { |
| 7 | ans = mid; |
| 8 | lo = mid + 1; |
| 9 | } else { |
| 10 | hi = mid - 1; |
| 11 | } |
| 12 | } |
| 13 | return ans; |
| 14 | } |
| 15 | } |
| 16 |
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
↑lo
↑hi
Variables
lo
0hi
10ans
0INITIALIZE
Search for the largest i with i² ≤ 10, over the range [0, 10].
Step 1 / 6
Approach & Solutions
Brute Force — Linear Scan
BruteTry i = 0, 1, 2, ... and stop as soon as (i + 1)² exceeds x — at that point i is the largest integer whose square doesn't exceed x. Correct, but it walks every candidate one at a time even though most of them could be ruled out much faster.
Time
O(√x)Space
O(1)Java
1class Solution {
2 public int mySqrt(int x) {
3 long i = 0;
4 while ((i + 1) * (i + 1) <= x) {
5 i++;
6 }
7 return (int) i;
8 }
9}Optimal — Binary Search
OptimalThe candidate answers 0..x are monotonic with respect to "i² ≤ x" — once i is too big, every larger i is too big as well. That monotonic split is exactly what binary search needs: search the range [0, x], and whenever mid² ≤ x, record mid as the best answer so far and try further right for something even bigger.
Time
O(log x)Space
O(1)Java
1class Solution {
2 public int mySqrt(int x) {
3 int lo = 0, hi = x, ans = 0;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 if ((long) mid * mid <= x) {
7 ans = mid;
8 lo = mid + 1;
9 } else {
10 hi = mid - 1;
11 }
12 }
13 return ans;
14 }
15}