#69
Sqrt(x)
Easy Binary search on the answer
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the integer square root of x (rounded down) without using a built-in power or sqrt function.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the biggest r with r × r ≤ x.
Why this works: "r² ≤ x" is true then false as r grows, so binary search r. Compare mid ≤ x / mid to avoid overflow.
Example: x = 8
mid 2: 2 ≤ 4 ✓ → ans 2, go rightmid 3: 3 ≤ 2 ✗ → go leftanswer 2
✦Hints open one at a time
The answer is the largest r with r × r <= x.
Binary search r in [0, x]; compare r with x / r to avoid overflow.
↗Approach
Search the answer space. If mid <= x / mid, mid is feasible — record it and go right; otherwise go left.
</>Solution (Java)
class Solution {
public int mySqrt(int x) {
if (x < 2) return x;
int lo = 1, hi = x / 2, ans = 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (mid <= x / mid) { // mid*mid <= x, without overflow
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
}!Common mistake
Computing mid * mid in int, which overflows for x near 2^31.
Complexity
- Time: O(log x).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon