This problem is about computing the floor of the square root of a number x using an optimized binary search approach. A best practice in binary search is to calculate the mid-point in a way that avoids integer overflow: m = l + (r - l) / 2.
Steps
- If
xis less than 2, returnx. - Set search boundaries:
l = 2,r = floor(x / 2). - Calculate mid-point safely:
m = l + floor((r - l) / 2). - Compare
m * mwithx. - If
m * m == x, returnm. - If
m * m > x, search left:r = m - 1. - If
m * m < x, search right:l = m + 1. - Return
rat the end — it will be the floor of √x.
Dry Run
Input: x = 4
- l = 2, r = 2 → m = 2
- 2 * 2 = 4 → return 2
Output: 2
Input: x = 8
- l = 2, r = 4 → m = 3 → 3*3 = 9 > 8 → r = 2
- l = 2, r = 2 → m = 2 → 2*2 = 4 < 8 → l = 3
- Loop ends → return r = 2
Output: 2
Time & Space Complexity
- Time Complexity: O(log x)
- Space Complexity: O(1)
var mySqrt = function(x) {
if (x < 2) return x;
let l = 2;
let r = Math.floor(x / 2);
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
if (x === m * m) {
return m;
} else if (x < m * m) {
r = m - 1;
} else {
l = m + 1;
}
}
return r;
};
#include <iostream>
using namespace std;
int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long long sq = 1LL * m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
#include <stdio.h>
int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
public class Solution {
public int mySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
}
def mySqrt(x: int) -> int:
if x < 2:
return x
l, r = 2, x // 2
while l <= r:
m = l + (r - l) // 2
if m * m == x:
return m
elif m * m > x:
r = m - 1
else:
l = m + 1
return r
public class Solution {
public int MySqrt(int x) {
if (x < 2) return x;
int l = 2, r = x / 2;
while (l <= r) {
int m = l + (r - l) / 2;
long sq = (long)m * m;
if (sq == x) return m;
if (sq > x) r = m - 1;
else l = m + 1;
}
return r;
}
}
