Implement int sqrt(int x).
Compute and return the square root of x. x is guaranteed to be a nonnegative integer. You can't use Math.sqrt function.
Example 1:
Input:4
Output:2
Example 2:
Input 8
Output 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
Approach #1 Brute Force [Accepted]
Intuition
Check all the integers up to x/2+1, find the maximum i where i*i<x.
Java
class Solution {
public int mySqrt(int x) {
if (x==0){
return 0;
}
for (int i =1;i<=x/2+1;i++){
if (i*i<=x && (double)(i+1)*(i+1)>x){
return i;
}
}
return 0;
}
}
Note: Please pay attention to Integer overflow. That's the reason why we convert the data type to double.
Complexity Analysis
 Time complexity : $$O(n)$$. For integer x, it takes on average x/2 steps to calculate the correct sqrt(x), hence the time complexity is O(n).
 Space complexity : $$O(1)$$.
Approach #2 Binary Division [Accepted]
Algorithm
This solution uses binary search approach.
Java
class Solution {
public int mySqrt(int x) {
if(x<2) return x;
int start = 1;
int end = 46340;
int mid,sq;
while(start<end){
mid = start + (end  start)/2;
sq = mid*mid;
if(sq == x){
return mid;
}else if(sq>x){
end = mid1;
}else {
start = mid+1;
}
}
return start*start>x?start1:start;
}
}
Complexity Analysis

Time complexity : $$O(log n)$$. For each element x, it will take log n time.

Space complexity : $$O(1))$$.
Approach #3 Newton's method [Accepted]
Algorithm
This solution uses Newton's method. Here are some links related to Newton's iteration for computing sqrt of X.
It is based on the fact that sqrt will be less than the half of the number.
Java
class Solution {
public int mySqrt(int x) {
if (x>=2147395600){
return 46340;
}
int ub=x;
int lb=1;
while(ub>lb)
{
ub=(int)Math.floor((lb+ub)/2);
lb=(int)Math.floor(x/ub);
}
return ub;
}
}
Complexity Analysis

Time complexity : Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with ndigit precision, provided that a good initial approximation is known, is $$O((\log n) F(n))$$ where F(n) is the cost of calculating f(x)/f'(x), with ndigit precision.

Space complexity : $$O(1))$$.