Problem Statement:
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.
Approach:
- If
xis less than2, 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.
Time & Space Complexity:
Time Complexity: O(logx)
Space Complexity: O(1)
Dry Run
Input: x = 8
Initial: if (x < 2) → false (since 8 ≥ 2) l = 2, r = Math.floor(8 / 2) = 4 Loop 1: m = l + Math.floor((r - l) / 2) = 2 + Math.floor((4 - 2) / 2) = 3 m * m = 9 8 < 9 → r = m - 1 = 2 Loop 2: m = l + Math.floor((r - l) / 2) = 2 + Math.floor((2 - 2) / 2) = 2 m * m = 4 8 > 4 → l = m + 1 = 3 Exit condition: l = 3, r = 2 → l > r → loop ends Return r = 2
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;
};
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;
}
}
#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;
}
}
