Problem
Given a non-negative integer x, return the floor of its square root (return type is int, so truncate).
Example
Input: 4
Output: 2Input: 8
Output: 2
sqrt(8) = 2.828, truncated to 2.Solution
Binary search the answer between 0 and x. Find the largest mid where mid * mid <= x.
def my_sqrt(x):
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = (left + right) // 2
if mid * mid <= x < (mid + 1) * (mid + 1):
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return left - 1function mySqrt(x) {
if (x < 2) return x;
let left = 1, right = Math.floor(x / 2);
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (mid * mid <= x && (mid + 1) * (mid + 1) > x) return mid;
if (mid * mid < x) left = mid + 1;
else right = mid - 1;
}
return left - 1;
}int mySqrt(int x) {
if (x < 2) return x;
long left = 1, right = x / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid <= x && (mid + 1) * (mid + 1) > x) return (int)mid;
if (mid * mid < x) left = mid + 1;
else right = mid - 1;
}
return (int)(left - 1);
}public int mySqrt(int x) {
if (x < 2) return x;
long left = 1, right = x / 2;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid <= x && (mid + 1) * (mid + 1) > x) return (int) mid;
if (mid * mid < x) left = mid + 1;
else right = mid - 1;
}
return (int)(left - 1);
}Complexity
- Time: O(log x)
- Space: O(1)
Explanation
Use long to avoid overflow when computing mid * mid for large x. Binary search narrows down to the floor of the true square root.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?