Easy Sqrt(x)
24%
Accepted
Implement int
sqrt(int x)
.
Compute and return the square root of x.
Have you met this question in a real interview?
Yes
Example
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
Challenge
O(log(x))
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
long lo = 0, hi = x/2 + 1;
while(lo <= hi){
long mid = (hi+lo)/2;
if (x < mid * mid) {
hi = mid-1; // not hi = mid
} else if(x > mid * mid) {
lo = mid+1;
} else return (int) mid;
}
return (int) hi;
}
}
Solution:
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
if(x <= 0) return x;
double last = 0, cur = 1;
while(last != cur){
last = cur;
cur = (cur + x/cur)/2;
}
return (int) cur;
}
}
Solution:
class Solution {
/**
* @param x: An integer
* @return: The sqrt of x
*/
public int sqrt(int x) {
// write your code here
if(x <= 0) return x;
double last = 0, cur = 1;
while(last != cur){
last = cur;
cur = (cur + x/cur)/2;
}
return (int) cur;
}
}
No comments:
Post a Comment