Problem
Implement int sqrt(int x)
.
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Solution
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
if (x < 2) return x;
var left = 1;
var right = x;
var mid = 0;
while (left <= right) {
mid = left + Math.floor((right - left) / 2);
if (mid > x / mid) {
right = mid - 1;
} else if ((mid + 1) > x / (mid + 1)) {
return mid;
} else {
left = mid + 1;
}
}
};
Explain:
nope.
Complexity:
- Time complexity : O(log(n)).
- Space complexity : O(1).