Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer.
The returned integer should be the greatest integer r such that r * r <= x.
You must not use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.
Example 1
Input
x = 4Output
2The square root of 4 is exactly 2.
Example 2
Input
x = 8Output
2The square root of 8 is approximately 2.828, so it rounds down to 2.
Constraints
- 0 <= x <= 2^31 - 1