LeetCode - Sqrt X
Problem description
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:
1
2
Input: 4
Output: 2
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.
Analysis
The first thought is to test from 1 to x/2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int mySqrt(int x) {
if (x == 0){
return 0;
}
for (int i = 0; i <= x/2; i++){
int temp = (i+1) * (i+1);
if (x == temp){
return i+1;
}
else if (x < temp || temp < 0){
return i;
}
}
return 0;
}
And we can transfer this problem into a search problem, which is to find a number in range 0 to x/2. So we can use binary search.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (x < 2){
return x;
}
int low = 1;
int high = x/2;
while (low <= high) {
int mid = low + (high - low)/2;
if (x / mid == mid){
return mid;
}
else if (x / mid > mid){
low = mid + 1;
}
else {
high = mid - 1;
}
}
return high;
Another solution from LeetCode is Newton’s Method, which performs best in all of the solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int mySqrt(int x) {
if (x < 2) return x;
double x0 = x;
double x1 = (x0 + x / x0) / 2.0;
while (Math.abs(x0 - x1) >= 1) {
x0 = x1;
x1 = (x0 + x / x0) / 2.0;
}
return (int)x1;
}
}
What to improve
- brute force is not good.
- we can use binary search to improve search efficiency.