Difficulty: Easy
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:
Example 2:
1
2
3
4
| Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
|
Solution
Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int start = 1, end = x;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (x / mid == mid) {
if (x % mid == 0) {
return mid;
} else {
end = mid;
}
} else if (x / mid > mid) {
start = mid;
} else {
end = mid;
}
}
if (x / end > end || x / end == end && x % end > 0) {
return end;
}
return start;
}
}
|