Description#
Implement the int sqrt(int x) function.
Compute and return the square root of x, where x is a non-negative integer.
Since the return type is an integer, the decimal part will be truncated.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842...,
but since the return type is an integer, the decimal part will be truncated.
Approach#
- Brute force solution, increment from 1 to find the square, return the value minus one if it exceeds x
int mySqrt(int x){
for(long i=1;;i++) {
if(i*i > x)
return (int)i-1;
}
}
Approach 2#
- Building on the previous approach, increase the increment span for a wider search range, then decrement to find the final value
int mySqrt(int x){
long first = 1;
for(;first < x;first *= 2)
if(first * first >= x)
break;
for(long second = first;;second--)
if(second * second <= x)
return second;
}