Binary SearchMath
Given a non-negative integer x, compute floor(sqrt(x)) without using a built-in square root function.
Input
A single integer x.
Output
Print the largest integer r such that r * r <= x.
Constraints
0 <= x <= 2^31 - 1
Example 1
Input
8
Output
2
2 * 2 = 4 <= 8 and 3 * 3 = 9 > 8.
Example 2
Input
16
Output
4
16 is a perfect square.