Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
Constraints:
0 <= x <= 2^31 - 1
My Solution
We can solve this problem efficiently with binary search. We also have to realize that x can be 2^31 - 1, which is the largest integer. Computing the square root for such a large number with binary search will lead to integer overflow. The trick is to use the integer type long to compute the squares of the intermediate integers. Doing it this way won’t lead to overflow. Finally if x is not a perfect square, binary search will end with the true exact square root existing between the integers start and end. We need to round down, so we just return end.
Time complexity would be O(log x) since we are using binary search. Space complexity would be O(1).
class Solution {
public int mySqrt(int x) {
long start = 0;
long end = x;
while (start <= end) {
long mid = start + (end-start)/2;
if (mid*mid == x) {
return (int)mid;
}
else if (mid*mid > x) {
end = mid-1;
}
else {
start = mid+1;
}
}
return (int)end;
}
}