Given a non-negative number num find the square root of the number.
If the square root is not a integer return the whole part. (Ex sqrt(10) = 3)
Try to do it without using system libraries.
Please note that n is less then 2**32.
Ex:
Input 1:
4
Output 1:
2
Explanation 1:
sqrt(4) = sqrt(2*2) = 2
Input 2:
99
Output 1:
9
Explanation 1:
sqrt(99) = 9.94 take the whole part => 9
Follow Up: Linear time algorithm is trivial, can you do it logarithmic time?