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
The brutal force way is to try all the numbers i from 2 to x/2, if i*i <= x and (i+1) >x, i is the value. The cost O(N) can be reduced to O(logN) with binary search.
public class SqureRoot {
public static int sqrt(int x) {
if(x==1) return 1;
if(x==2) return 1;
//8
int lo = 2;
int hi = x/2; //4
while(lo < hi) {
int mid = lo + (hi - lo)/2;//3
int sqr = mid*mid;
if(sqr < x) lo = mid+1;
else if(sqr > x) hi = mid - 1;//2
else return mid;
}
return lo;
}
public static void main(String...args) {
System.out.println(sqrt(4));
System.out.println(sqrt(8));
}
}
public static int sqrt(int x) {
if(x==1) return 1;
if(x==2) return 1;
//8
int lo = 2;
int hi = x/2; //4
while(lo < hi) {
int mid = lo + (hi - lo)/2;//3
int sqr = mid*mid;
if(sqr < x) lo = mid+1;
else if(sqr > x) hi = mid - 1;//2
else return mid;
}
return lo;
}
public static void main(String...args) {
System.out.println(sqrt(4));
System.out.println(sqrt(8));
}
}
The Time cost is O(logN), the space cost is O(1).
